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

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

תיאור

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

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

זיהוי שפות ומשפחות של מעגלים

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

ההכללה הזו מתבצעת על ידי בחינת משפחה של מעגלים בוליאניים. משפחה שכזו $\ C$ היא סדרה $\ C_{0},C_{1},C_{2}\dots$ של מעגלים כך שלמעגל $\ C_{n}$ בדיוק n ביטי קלט. כעת ניתן להגדיר את השפה שמתקבלת על ידי $\ C$ בצורה הבאה: $\ L(C)=\left\{x\mid C_{|x|}(x)=1\right\}$, כלומר אוסף המילים שהמעגל המתאים מחזיר עליהן את הערך 1 ("מקבל" אותן).

יוניפורמיות של מעגלים

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

דוגמה בסיסית היא זו: כל שפה אונרית (שפה שכל מילה בה מורכבת מרצף של 1 בלבד) $\ L$ ניתנת לקבלה על ידי משפחת מעגלים בוליאניים, שכן אם $\ 1^{n}\in L$ הרי שהמעגל על $\ n$ קלטים שמחזיר תמיד 1 מקבל את המילה, ואם $\ 1^{n}\notin L$, המעגל על $\ n$ קלטים שמחזיר תמיד 0 דוחה אותה, ומכאן שסדרת המעגלים המתאימה מקבלת את $\ L$. עם זאת, ידוע כי קיימות משפחות של שפות אונריות שאינן ניתנות לקבלה על ידי אף מכונת טיורינג (למשל, משיקולי ספירה: קיים מספר בן מנייה של מכונות טיורינג אך מספר לא בן מנייה של שפות אונריות).

על כן, כדי לקשור את המעגלים הבוליאניים למכונות הטיורינג נוהגים לרוב לעסוק במשפחות יוניפורמיות של מעגלים בוליאניים - משפחות שניתנות לחישוב באמצעות מכונת טיורינג. כלומר, משפחת מעגלים $\ C=\left\{C_{0},C_{1},\dots \right\}$ היא יוניפורמית אם קיימת מכונת טיורינג שעל הקלט $\ n$ מוציאה כפלט קידוד מוסכם של $\ C_{n}$.

קישורים חיצוניים

• גדי אלכסנדרוביץ', מעגלים בוליאניים – מה זה בכלל?, באתר "לא מדויק",