מכונת טיורינג
מודל חישוב עם סרטים, ראשי קריאה/כתיבה ומצב בקרה.
מילון דו־לשוני
המונחים נשמרים באופן עקבי לאורך כל הקורס.
מכריע
מכונה שחייבת לעצור על כל קלט ולהחזיר קבלה או דחייה.
קונפיגורציה
תיאור רגעי מלא של ריצת מכונה: מצב, תוכן סרטים ומיקומי ראשים.
גרף קונפיגורציות
גרף שבו קודקוד הוא קונפיגורציה וקשת היא מעבר חוקי יחיד.
קידוד
ייצוג של מופעים, מכונות או מספרים כמחרוזות על אלפבית סופי.
זמן פולינומיאלי
גבול זמן ריצה שחסום על ידי פולינום באורך הקלט המקודד.
DTIME
מחלקת השפות שמכונות דטרמיניסטיות מכריעות בזמן $O(t(n))$.
DSPACE
מחלקת השפות שמכונות דטרמיניסטיות מכריעות במקום $O(s(n))$.
P
איחוד כל מחלקות DTIME פולינומיאליות; שפות הניתנות להכרעה בזמן פולינומיאלי.
PSPACE
שפות הניתנות להכרעה במקום פולינומיאלי.
משפט היררכיה
תוצאה שמוכיחה שיותר משאב (זמן או מקום) מאפשרת להכריע יותר שפות.
ריפוד / ניפוח
הגדלת אורך הקלט בלי לשנות את ההכרעה המקודדת.
מכונה אי־דטרמיניסטית
מכונה שמקבלת אם קיים לפחות ענף חישוב מקבל.
עץ חישוב
עץ שבו כל צומת הוא קונפיגורציה וכל יורש מייצג בחירת מעבר חוקית.
עד / תעודה
מחרוזת קצרה שמאפשרת למוודא לאשר מופע כן.
תעודה
עד פולינומיאלי שמצורף למופע ונבדק על ידי מוודא.
מוודא
מכונה פולינומית הבודקת זוג של מופע ותעודה.
NP
שפות שיש להן תעודה פולינומיאלית הניתנת לאימות בזמן פולינומיאלי.
coNP
שפות שמשלימן ב-NP; מופע לא מוכח על ידי תעודה קצרה.
רדוקציה כמהדר מופעים פולינומיאלית
התמרה $f$ הניתנת לחישוב בזמן פולינומיאלי כך ש-$x\in A\iff f(x)\in B$.
רדוקציה
התמרה חישובית המשמרת שייכות לשפה.
רדוקציה קנונית
רדוקציה סטנדרטית ומוכרת ברשת הבעיות, למשל מ-3SAT ל-IS.
בעיות שלמות קנוניות
משפחת בעיות NP-שלמות מרכזיות (SAT, IS, CLIQUE, TSP וכו') ורשת הרדוקציות ביניהן.
טרנזיטיביות
אם $A\le_m^p B$ ו-$B\le_m^p C$, אז $A\le_m^p C$; הרכבה של רדוקציות.
סגירות כלפי מטה
אם $A\le_m^p B$ ו-$B\in\mathrm P$, אז $A\in\mathrm P$; אותו עיקרון ל-NP ו-coNP.
NP-קשה
לפחות קשה כמו כל שפה ב-NP תחת הרדוקציה הנתונה; אינה חייבת להיות ב-NP.
NP-שלמה
בעיה ב-NP שכל בעיה ב-NP ניתנת לרדוקציה אליה.
משפט Cook–Levin
SAT היא NP-שלמה; כל שפה ב-NP ניתנת לרדוקציה אליה באמצעות טבלת חישוב.
טבלת חישוב
מטריצה שבה כל שורה היא קונפיגורציה מלאה של מכונה על קלט נתון.
גאדג׳ט
רכיב משני בבניית רדוקציה שמקודד אילוץ מקומי (פסוקית, משתנה, צלע).
הוכחת אם־ורק־אם
הוכחה דו־כיוונית: מופע כן ביעד $\iff$ מופע כן במקור.
CNF / צורה נורמלית קונjunctive
נוסחה בוליאנית כמכפלה של פסוקיות (OR של ליטרלים).
3SAT
SAT שבו כל פסוקית מכילה בדיוק שלושה ליטרלים.
קבוצה בלתי־תלויה (IS)
בגרף: קבוצת קודקודים שאין ביניהם צלעות.
קליקה
בגרף: קבוצת קודקודים שכל זוג מהם שכנים.
כיסוי קודקודים (VC)
קבוצת קודקודים שכל צלע נוגעת לפחות באחד מהם.
משלים גרף
גרף עם אותם קודקודים וצלעות הפוכות: $\{u,v\}\in E(\overline G)\iff\{u,v\}\notin E(G)$.
הכרעה מול אופטימיזציה
בעיית הכרעה מחזירה ביט; בעיית אופטימיזציה מבקשת את הפתרון או את ערך המטרה.
זמן פסאודו־פולינומיאלי
זמן פולינומיאלי בערכי המספרים אך מעריכי באורך הקידוד הבינרי.
NP-קושי בחוזקה
קושי שנשמר גם כשערכי המספרים חסומים פולינומיאלית.
יחס קירוב
חסם המשווה פתרון אלגוריתמי לפתרון האופטימלי.
היוריסטיקה
שיטה שעובדת טוב בניסוי אך ללא הבטחת קירוב או אופטימליות.
מכונת טיורינג הסתברותית
מכונה עם גישה לביטים אקראיים; לאחר בחירת $r$ הריצה דטרמיניסטית.
מונטה קרלו
אלגוריתם אקראי עם זמן קבוע שעלול לטעות בהסתברות חסומה.
לאס וגאס
אלגוריתם אקראי שתמיד נכון; זמן הריצה אקראי וחסום בתוחלת.
BPP
שפות הניתנות להכרעה בזמן פולינומיאלי עם שגיאה דו־צדדית חסומה.
הגברה
הפחתת הסתברות שגיאה על ידי חזרה על אלגוריתם אקראי.
L
שפות הניתנות להכרעה במקום לוגריתמי $O(\log n)$.
NL
שפות שמכונות אי־דטרמיניסטיות מכריעות במקום לוגריתמי.
STCON
בעיית נגישות: האם יש מסלול מ-$s$ ל-$t$ בגרף מכוון?
רדוקציה במקום לוגריתמי
רדוקציה שמחשבת את הפלט בלי לשמור אותו במלואו; טרנסדיוסר לוגריתמי.
טרנסדיוסר
מכונה שמדפיסה פלט תוך שמירה על חסם מקום.
גרף מרומז
גרף שלא נשמר במלואו; שכנות נבדקת או נוצרת לפי דרישה.
משפט סביץ'
$\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(s(n)^2)$; בפרט $\mathrm{NL}\subseteq\mathrm L$.
אורקל
שאילתת קופסה שחורה לשפה הנענית בצעד חישוב אחד.
ההיררכיה הפולינומיאלית (PH)
מחלקות $\Sigma_k^P$ ו-$\Pi_k^P$ עם $k$ בלוקים מתחלפים של כמתים קיומיים ואוניברסליים.
רלטיביזציה
הוכחה שממשיכה להיות נכונה ביחס לכל אורקל; מגבילה טכניקות הפרדה.
P/poly
שפות הניתנות להכרעה על ידי מעגלים לא אחידים בגודל פולינומיאלי.
מעגל בוליאני
רשת של שערים AND, OR, NOT שמחשבת פונקציה בוליאנית.