NP ביניים

בתורת הסיבוכיות, NP ביניים היא מחלקת כל בעיות ההכרעה במחלקה NP שאינן נמצאות ב-P וגם אינן NP-שלמות (NPC). המחלקה של בעיות אלו נקראת NPI. נשים לב שאם P=NP, אזי NPI היא ריקה. הכיוון השני גם כן נכון, כלומר אם $P\neq NP$ , אזי NPI אינה ריקה. תוצאה לא טריוויאלית זו נובעת ממשפט לדנר, שהוכח בשנת 1975 על ידי ריצ'רד לדנר. משפט לדנר קובע שאם $P\neq NP$ , אזי NPI אינה ריקה.

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

משפט לדנר

משפט לדנר קובע שאם המחלקות P ו-NP שונות אחת מהשנייה, אזי קיימת שפה שאינה NP-שלימה ואינה ב-P.

נוכיח את המשפט בשתי דרכים שונות. שתי הדרכים משתמשות בשיטת הוכחה בלכסון.

הוכחה עם חירור SAT

תהיינה $\{M_{i}\}_{i=1}^{\infty }$ כל המכונות הפולינומיות אשר רצות לכל היותר בזמן $|x|^{i}$ כל אחת, ותהיינה באופן דומה $\{f_{i}\}_{i=1}^{\infty }$ כל הפונקציות הפולינומיות שרצות בזמן לכל היותר $|x|^{i}$ . נשים לב שכל המכונות הפולינומיות וכל הפונקציות הפולינומיות נמצאות כאן.

נגדיר שפה -

A=\{x|x\in SAT\ \ {\text{and }}f(|x|){\text{ is even}}\}

ברור שאם הפונקציה f חשיבה בזמן פולינומי אזי $A\in NP$ .

נגדיר את הפונקציה f כך: $f(0)=f(1)=2$ . עבור $n\geq 1$ נגדיר את $f(n+1)$ :

אם $log^{f(n)}(n)\geq n$ אז נשאיר את $f(n+1)=f(n)$

אחרת יש לנו שני מקרים:

$f(n)=2i$ (כלומר ערך זוגי), נבדוק האם קיים קלט x, $|x|\leq log(n)$ כך ש-

$M_{i}(x)$ מקבלת את x וגם $f(|x|)$ אי-זוגי או $x\notin SAT$ , או
$M_{i}(x)$ דוחה את x וגם $f(|x|)$ זוגי או $x\in SAT$

אם קיים כזה x, אזי

f(n+1)=f(n)+1

. אחרת

f(n+1)=f(n)

.

$f(n)=2i+1$ (כלומר ערך אי זוגי), נבדוק האם קיים קלט x, $|x|\leq log(n)$ כך ש-

$x\in SAT$ וגם מתקיים $f(|f_{i}(x)|)$ אי-זוגי או $f_{i}(x)\notin SAT$
$x\notin SAT$ וגם $f(|f_{i}(x)|)$ זוגי וגם $f_{i}(x)\notin SAT$

אם קיים כזה x, אזי בדומה למקודם,

f(n+1)=f(n)+1

. אחרת

f(n+1)=f(n)

.

עכשיו נסביר מדוע זה עובד.

ראשית כל נשים לב שאין קשר בין הפונקציות $f_{i}$ לפונקציה $f$

מתקיים שהסדרה של המכונות הפולינומיות שלנו לא יכולות לפתור את SAT, מכיוון שהנחנו ש- $P\neq NP$ , ולכן יש גם אינסוף xים שהמכונה נכשלת עליהם, כלומר לכל מספר טבעי n קיים x באורך גדול או שווה ל-n שהמכונה נכשלת עליו. לכן אם המכונה מקבלת את x אבל x בכלל לא ב-SAT, אז מתקיים שהמכונה הזאת כבר לא תוכל להכריע את השפה שהגדרנו A, מכיוון ש-x יהיה בשפה A (שהרי $f(n)$ זוגי וגם x לא ב-SAT).

באופן אנלוגי נותנים את התנאי השני. אם המכונה לא מקבלת את x אבל x כן ב-SAT, אז מצאנו שוב x שהמכונה $M_{i}$ נכשלת עליו. אחרי שהבנו איך הבניה מפרידה את SAT מכל מכונה פולינומית, נסביר בקצרה את העניין עם הפונקציה $f$ . השימוש בפונקציה הזו נועד כדי שנוכל לסנן עוד מילים מהשפה, כדי שהיא לא תהיה NPC (שלמה). לכן בכל תנאי, במקום לדרוש המילה תהיה או לא תהיה ב-SAT, אנחנו דורשים שהמילה תהיה או לא תהיה ב-A, כלומר מוסיפים את הדרישה ש- $f(|x|)$ זוגי. ברור שנמצא x כזה, כי הנחנו ש- $P\neq NP$ , אז אין לכל מכונה פולינומית יש קלט x עבורו היא מחזירה תשובה לא נכונה.

עתה סיימנו להוכיח רעיונית שהשפה A אינה נמצאת ב-P. נרצה להוכיח שהשפה גם אינה NPC, כלומר לא קיימת רדוקציה פולינומית מ-SAT אל A. כמו שהגדרנו מקודם, יש לנו רשימה של כל הפונקציות הפולינומיות הקיימות. אם השפה A היא אכן NPC אזי אחת מהפונקציות היא רדוקציה פולינומית מ-SAT אל A. לכן אנחנו מחפשים עבור כל פונקציה $f_{i}$ קלט x עבורו הפונקציה לא מהווה רדוקציה ל-A (וכתוב למעלה איך עושים את זה פורמלית בדיוק). כעת נותר להוכיח שהתנאים לבסוף מתקיימים, כלומר שאין איזה i עבורו $f_{i}$ כן מהווה רדוקציה ל-SAT. לכל פונקציה $f_{i}$ שהיא רדוקציה ל-SAT, מההנחה ש $P\neq NP$ אורך הפלט של הפונקציה $f_{i}$ גדל^[1], ולכן בסופו של דבר נגיע ל- $|f_{i}(x)|$ מספיק גדול שיהיה אי-זוגי^[2] ונגרום לכך ש- $f_{i}$ לא תהיה רדוקציה טובה.

הדרישה שאם $log^{f(n)}(n)\geq n$ אז $f(n+1)=f(n)$ נועדה כדי שבכל שלב נוכל להשתמש בפונקציות $f(|f_{i}(x)|)$ ^[3] בסך הכל הוכחנו בחלק הראשון ש-A לא ב-P, ובחלק השני שאין רדוקציה פולינומית מ-SAT ל-A, ולכן הפונקציה A נמצאת ב-NPI, כדרוש.

הוכחה עם ריפוד SAT

נגדיר את $\{M_{i}\}_{i=1}^{\infty },\{f_{i}\}_{i=1}^{\infty }$ כמקודם.

נגדיר שפה $L=\{\phi 01^{f(n)-|n|-1}|\phi \in SAT\land |\phi |=n\}$

אנחנו נשאיר את $f(n)=n^{i}$ עד שנקיים את התנאי ה-i, ואז נקדם את $f(n)$ להיות $f(n)=n^{i+1}$

כעת נתאר אלגוריתם לחישוב $f(n)$ . נתחיל עם $i=1$ . לכל n נבצע את הפעולות הבאות: $f(n)=n^{i}$ . נבדוק האם קיים קלט $|x|\leq log(n)$ , כך שמתקיים:

$M_{i}(x)$ מקבל את x, אבל $x\notin L$
$M_{i}(x)$ דוחה את x, אבל $x\in L$

במידה ויש כזה x, נגדיר $i=i+1$ . אחרת לא נשנה את i ונעבור ל-n הבא.

מכיוון שאנחנו בודקים רק עבור $|x|\leq log(n)$ ניתן לחשב את f בזמן פולינומי

ברור שהבנייה לא נתקעת על i מסוים, מכיוון שבמקרה כזה הייתה רדוקציה טריוויאלית מ-SAT ל-L, אבל המכונות $M_{i}$ הן פולינומיות, וזה סותר את ההנחה $P\neq NP$ .

לכן מילאנו את התנאי שהשפה L אינה פולינומית. כעת נניח שיש פונקציה $f_{j}(\cdot )$ עושה רדוקציה פולינומית מ-SAT ל-L. נרצה להראות שזה גורר ש-SAT פתירה בזמן פולינומי (וכנגד ההנחה שלנו, כמובן)

הוכחה. מאחר ש $f_{j}(x)$ רצה לכל היותר בזמן $|x|^{j}$ , מתקיים $|f_{j}(\phi )|\leq |\phi |^{j}$ ^[4]. חייב להיות $n_{0}$ כך שלכל $n\geq n_{0}$ מתקיים $f(n)=n^{k},k>j$ . מכיוון ש- $n_{0}$ קבוע, אפשר פשוט לפתור את כל הבעיות מאורך קטן או שווה לו בזמן אקספוננציאלי.

עכשיו נניח שיש לנו נוסחה $\phi$ כך ש $|\phi |\geq n_{0}$ . אם $f_{j}(\phi )$ לא בטווח של $f$ , אז $f_{j}(\phi )\notin L\implies \phi \notin SAT$ . אחרת, $f_{j}(\phi )=\psi 01^{f(m)-m-1}$ כש- $m=|\psi |$ ו $\phi \in SAT$ אם ורק אם $\psi \in SAT$ . עד כה השגנו ש $f(m)\leq f_{j}(\phi )<|\phi |^{j}$ . אז $|\psi |=m\leq |\phi |^{j/k}$ אם $f(m)=m^{k}$ . מאחר ש $|\phi |>n_{0}$ מתקיים ${\ce {k>j}}$ אז $|\psi |<|\phi |$ . אם $|\psi |\leq n_{0}$ אז אפשר לבדוק אם $\psi$ ב-SAT ולכן גם אפשר לבדוק אם $\phi$ ב-SAT. אחרת נריץ את האלגוריתם רקורסיבית (לא יותר מ-n פעמים) מכיוון שגודל הפלט גדל בין הרצה להרצה, וכל ריצה מתבצעת בזמן פולינומי.