שתי שאלות בסיבוכיות.

[gil levi]

שתי שאלות בסיבוכיות.

היי, השאלות בתמונה המצורפת, מסומנת במסגרת אדומה (כלומר, שאלה 1a ו2a). לגבי 1a: מצוין שניתן להשתמש בשערים עם מספר קלטים גדול, אז חשבתי פשוט להשתמש בשער XOR אחד שיקבל את כל המשתנים. זה עובד , אבל מצוין שצריך שגודל המעגל (מספר הצמתים) יהיה O(n*s^sqrt)zzz ובפתרון שננתי זה רק שער אחד. ניסיתי לממש XOR כזה באמצעות שערים אחרים, אבל אז אני לא מצליח להגיע לעומק קבוע. לגבי 2a: אשמח לקבל הכוונה או פתרון למקרה פרטי (n=3 למשל). תודה, גיל.

 

[gil levi]

שאלה נוספת בסיבוכיות.

היי, השאלה בתמונה המצורפת. לגבי הסימון SIZE(n^2)zz: הגדרה: משפחה של מעגלים בוליאניים מגודל T zzz היא סידרה C_n (n=1 to inf) zzz, כאשר C_n הוא מעגל בוליאני עם n קלטים ופלט אחד שמקיים T = |C_n| zzz (כאשר |C_n| הוא מספר הצמתים במעגל). נגדיר SIZE(T)zzz להיות מחלקת השפות L⊆{0,1}* zzz עבורן קיימת משפחת מעגלים בגודל O(T)zzz כך שלכל n טבעי:

∀ x∈{0,1}*, x∈L ↔ C_n(x) =1​

נחזור לשאלה: מה שמבקשים זה בעצם להראות שכל פונקציה (או שפה) הניתנת לחישוב על ידי מעגל בגודל n ניתנת לחישוב על ידי מעגל בגודל n^2 ושקיימת פונקציה (או שפה) הניתנת לחישוב על ידי מעגל בגודל n^2 אבל לא ניתנת לחישוב על ידי מעגל בגודל n. הכיוון שלי הוא הכיוון הבא: נסמן בA את מספר הפונקציות (באופן שקול -שפות) הניתנות לחישוב על ידי מעגלים בגודל n^2 ובB את מספר המעגלים בגודל n ונראה ש A>B. אני חושב שאת B אני יודע לחשב, אבל אין לי מושג איך לחשב את A. כלומר, השאלה שלי היא בעצם כמה פונקציות קיימות הניתנות לחישוב על ידי מעגלים בגודל n^2? תודה, גיל.