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

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

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

כדי לטפל בקלטים בגדלים שונים בודקים משפחה של מעגלים. משפחה היא סדרה C_0,C_1,C_2,… שבה לכל n קיים מעגל C_n שקולט בדיוק n ביטים. כך מקשרים בין מעגלים לבעיות של זיהוי שפות פורמליות: שפה שמתקבלת ממשפחה C כוללת את כל המילים שהמעגל המתאים להן מקבל.

בעיה מרכזית היא שהתיאור של משפחה יכול להיות בלתי מוגבל ומוזר, ולכן לא תמיד מייצג אלגוריתם סופי. יש משפחות מעגלים שמכריעות שפות שאינן ניתנות להכרעה על ידי מכונת טיורינג. דוגמה פשוטה היא משפחות עבור שפות אונריות (מילים שמורכבות רק מאותיות 1): ניתן לבנות מעגל לכל n שמחזיר תמיד 1 או תמיד 0, ולכן כל שפה אונרית מקבלת משפחה. מצד שני קיימות שפות אונריות שגודלן גדול מדי כדי שמכונת טיורינג תוכל לקבלן.

כדי למנוע אי-סדרים כאלה מגדירים יוניפורמיות: משפחה היא יוניפורמית אם קיימת מכונת טיורינג שמקבלת n ומוציאה קידוד של המעגל C_n. כלומר, יש כללים חישוביים ברורים שיוצרים את המעגלים בסדרה.

סיבוכיות מעגלים עוסקת במעגלים בוליאניים. מעגל בוליאני הוא רשת שערים לוגיים. שער לוגי הוא רכיב שמחליט על 0 או 1. AND מחזיר 1 רק אם כל הקלטים הם 1. OR מחזיר 1 אם לפחות קלט אחד הוא 1. NOT הופך 0 ל-1 ולהפך. למעגל יש כניסות ביטים ויציאה אחת.

מעגלים מחוברים זה לזה כדי לחשב תשובה על קלט נתון. יש מעגלים קטנים יותר ומעגלים גדולים יותר. העבודה במעגלים בודקת כמה גדולים וכמה עמוקים צריכים להיות המעגלים כדי לפתור בעיה.

כשיש מילים בגדלים שונים בונים משפחה של מעגלים. משפחה היא רצף מעגלים C_0,C_1,C_2,… שבו C_n מתאים לכניסה של n ביטים. השפה שהמשפחה מקבלת היא כל המילים שהמעגל המתאים להן מחזיר 1.

לעתים משפחות יכולות להיות מאוד מוזרות. לפעמים אין תיאור פשוט שמייצר את המעגלים. לכן דורשים יוניפורמיות. יוניפורמיות אומרת שיש "מחשב תיאורטי" (מכונת טיורינג) שמקבל מספר n ומוציא תיאור של המעגל C_n. כך יודעים שצריך להיות כלל ברור לבניית המעגלים.