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

