מפת הסיבוכיות
EN
טבלת חישוב וחלונות 2×3

A ∈ NP ≤p SAT

לכל שפה A∈NPA\in\mathrm{NP} מתקיים A≤pSATA\le_p\mathrm{SAT}. זהו משפט קוק–לוין: SAT\mathrm{SAT} היא NP-קשה, ומכיוון שגם SAT∈NP\mathrm{SAT}\in\mathrm{NP} — היא NP-שלמה.

הבנייה

תהי A∈NPA\in\mathrm{NP}, ותהי MM מכונה אי-דטרמיניסטית המכריעה את AA בזמן q(n)q(n) פולינומי. על קלט xx באורך nn:

  1. הטבלה. נתבונן בטבלה TM,xT_{M,x} בגודל q(n)×q(n)q(n)\times q(n): שורה ii מקודדת את הקונפיגורציה של MM אחרי ii צעדים, כמחרוזת אחת שבה מצב המכונה נכתב משמאל לתו שעליו עומד הראש. הטבלה רחבה דיה כי בזמן q(n)q(n) הראש אינו יכול להתרחק יותר מ-q(n)q(n) תאים.
  2. המשתנים. לכל תא (i,j)(i,j) ולכל סמל ss באלפבית L=Γ∪Q∪{#}L=\Gamma\cup Q\cup\{\#\} נגדיר משתנה בוליאני xi,j,sx_{i,j,s}, שמשמעותו "בתא (i,j)(i,j) כתוב הסמל ss".
  3. הנוסחה. φ=φcell∧φstart∧φaccept∧φmove\varphi=\varphi_{cell}\wedge\varphi_{start}\wedge\varphi_{accept}\wedge\varphi_{move}:
    • φcell\varphi_{cell} — בכל תא כתוב בדיוק סמל אחד;
    • φstart\varphi_{start} — השורה הראשונה היא הקונפיגורציה ההתחלתית על xx;
    • φaccept\varphi_{accept} — אי-שם בטבלה מופיע המצב המקבל;
    • φmove\varphi_{move} — כל חלון 2×32\times3 בטבלה הוא חלון חוקי, כלומר עקבי עם פונקציית המעברים של MM.
  4. החזר את ⟨φ⟩\langle\varphi\rangle.

הלב של הבנייה הוא סעיף φmove\varphi_{move}: חוקיות גלובלית של החישוב נאכפת על ידי אוסף של בדיקות מקומיות בלבד. שתי שורות עוקבות מייצגות מעבר חוקי של MM אם ורק אם כל חלון 2×32\times3 שלהן חוקי — כי בצעד יחיד משתנים רק התא שתחת הראש ושכניו.

המחשה

בנייה מודרכת

טבלת קוק–לוין

שלב 1 מתוך 7
קלט x = 10 · חסם זמן T = 3 · רוחב הטבלה S = 5
t=0
⊢
[q0,1]
0
□
□

נכונות — שני הכיוונים

A ∈ NP ∈ ⟹ SAT ∈

נניח x∈Ax\in A. אזי קיימת ריצה מקבלת של MM על xx באורך ≤q(n)\le q(n). נמלא את הטבלה לפי אותה ריצה בדיוק, ונגדיר השמה: xi,j,s=1x_{i,j,s}=1 אם ורק אם בתא (i,j)(i,j) של הטבלה הזאת כתוב ss.

ההשמה מספקת את ארבעת החלקים: φcell\varphi_{cell} מסופק כי בכל תא כתוב סמל יחיד; φstart\varphi_{start} מסופק כי מילאנו את השורה הראשונה בקונפיגורציה ההתחלתית; φaccept\varphi_{accept} מסופק כי הריצה מקבלת ולכן המצב המקבל מופיע; φmove\varphi_{move} מסופק כי כל שתי שורות עוקבות מתארות צעד חוקי של MM, ולכן כל חלון 2×32\times3 חוקי. לכן φ\varphi ספיקה.

SAT ∈ ⟹ A ∈ NP ∈

נניח ש-φ\varphi ספיקה, ותהי π\pi השמה מספקת. נקרא ממנה טבלה: מכיוון ש-π\pi מספקת את φcell\varphi_{cell}, לכל תא (i,j)(i,j) יש בדיוק סמל אחד ss עם π(xi,j,s)=1\pi(x_{i,j,s})=1, ולכן הטבלה מוגדרת היטב.

מכיוון ש-π\pi מספקת את φstart\varphi_{start}, השורה הראשונה היא הקונפיגורציה ההתחלתית על xx. מכיוון שהיא מספקת את φmove\varphi_{move}, כל חלון 2×32\times3 חוקי, ולכן — באינדוקציה על השורות — כל שורה מתקבלת מקודמתה בצעד חוקי של MM. כלומר הטבלה מתארת ריצה אמיתית של MM על xx. מכיוון ש-π\pi מספקת את φaccept\varphi_{accept}, בריצה הזאת מופיע המצב המקבל. לכן קיימת ריצה מקבלת של MM על xx, ומכאן x∈Ax\in A.

סיבוכיות הרדוקציה

זמןO(q(n)^2) up to polylog factors
מקוםO(q(n)^2)
גודל הפלטO(q(n)^2 · |L| · log q(n)) bits

הטבלה היא q(n)×q(n)q(n)\times q(n) תאים, ולכל תא ∣L∣|L| משתנים — כלומר O(q(n)2)O(q(n)^2) משתנים, ו-∣L∣|L| הוא קבוע שאינו תלוי בקלט (הוא נקבע על ידי MM בלבד). φmove\varphi_{move} מכיל פסוקית לכל חלון, ומספר החלונות הוא (q(n)−1)⋅(q(n)−2)=O(q(n)2)(q(n)-1)\cdot(q(n)-2)=O(q(n)^2); מספר השישיות האפשריות לחלון הוא ∣L∣6|L|^6, שוב קבוע. לכן ∣φ∣=O(q(n)2)|\varphi|=O(q(n)^2) עד כדי קבועים ו-log⁡\log לקידוד אינדקסים — פולינומי בגודל הקלט, וזה כל מה שנדרש.

מה זה קונה

SAT\mathrm{SAT} היא NP-שלמה. זו הבעיה הראשונה שקושייה הוכחה מאפס — כל שאר הרדוקציות בקורס נשענות עליה דרך הטרנזיטיביות של ≤p\le_p.

מלכודות

  • הרדוקציה בונה את הנוסחה מ-⟨M⟩\langle M\rangle ומ-xx בלבד. היא אינה מריצה את MM ואינה יודעת אם קיימת ריצה מקבלת — הטבלה המלאה מופיעה רק בהוכחת הנכונות, שם מותר להניח "קיימת ריצה מקבלת".

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

השרשרת

משמשת בהמשך ל

מאיפה זה נקרא