סיבוכיות מעגלים

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לשכתב ערך זה
ייתכנו לכך מספר סיבות: ייתכן שהמידע המצוי בדף זה מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים לוויקיפדיה. אתם מוזמנים לסייע ולתקן את הבעיות בדף זה, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה שלו.

סיבוכיות מעגלים עוסקת בשאלה איזה בעיות הכרעה ניתן לפתור באמצעות מעגלים לוגיים (המורכבים משערי OR,AND ו-NOT) בעלי עומק "קטן" וגודל פולינומי. כמו כן מבחינים בין שערים בהם דרגת הכניסה היא חסומה ולא חסומה.

המחלקה \ NC_{k} מכילה את הבעיות הניתנות להכרעה על ידי מעגל לוגי בעומק \ O(log^{k}n), גודל פולינומי ודרגת כניסה חסומה.

המחלקה \ AC_k מכילה את הבעיות הניתנות להכרעה על ידי מעגל לוגי בעומק \ O(log^{k}n), גודל פולינומי ודרגת כניסה לא חסומה.

המחלקה \ AC מוגדרת כ: \ AC = \bigcup\limits_k {AC_k}


בדומה, המחלקה NC מוגדרת כ: \ NC = \bigcup\limits_k {NC_k}.

בעיות הנמצאות במחלקה NC נחשבות לבעיות הניתנות למיקבול.

[עריכה] תכונות ידועות

עבור כל \ k ניתן להראות ש-\ AC_k \subseteq NC_{k+1} על ידי החלפת כל שער שדרגתו לא חסומה ב-\ logn שערים בעלי דרגה חסומה.

מכך נובע ש-\ AC=NC.

כמו כן ידוע ש-\ XOR_n \in NC_{1}-AC_{0} ולכן \ AC_0 \subset NC_1.

[עריכה] שאלות פתוחות

האם קיים \ i>0 עבורו \ AC_i \subset NC_{i+1}?