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

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