NP ביניים

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

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

נוכיח את המשפט בשתי דרכים שונות. שתי הדרכים משתמשות בשיטת הוכחה בלכסון. 
===הוכחה עם חירור SAT===
תהיינה <math>\{M_i\}_{i=1}^\infty </math> כל המכונות הפולינומיות אשר רצות לכל היותר בזמן <math>|x|^i </math> כל אחת, ותהיינה באופן דומה <math>\{f_i\}_{i=1}^\infty </math> כל הפונקציות הפולינומיות שרצות בזמן לכל היותר <math>|x|^i </math>. נשים לב שכל המכונות הפולינומיות וכל הפונקציות הפולינומיות נמצאות כאן.

נגדיר שפה - 
: <math>A = \{x | x \in SAT\ \ \text{and } f(|x|) \text{ is even} \}</math>
ברור שאם הפונקציה f חשיבה בזמן פולינומי אזי <math>A \in NP</math>.

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

אם <math>log^{f(n)}(n) \ge n</math> אז נשאיר את <math>f(n+1)=f(n)</math>

אחרת יש לנו שני מקרים: 
*<math>f(n)=2i</math> (כלומר ערך זוגי), נבדוק האם קיים קלט x, <math>|x| \leq log(n)</math> כך ש-
#<math>M_i(x)</math> מקבלת את x וגם <math>f(|x|)</math> אי-זוגי או <math>x \notin SAT</math>, או
#<math>M_i(x)</math> דוחה את x וגם <math>f(|x|)</math> זוגי או <math>x \in SAT</math>
::אם קיים כזה x, אזי <math>f(n+1) = f(n) + 1</math>. אחרת <math>f(n+1) = f(n)</math>.
*<math>f(n)=2i+1</math> (כלומר ערך אי זוגי), נבדוק האם קיים קלט x, <math>|x| \leq log(n)</math> כך ש-
#<math>x \in SAT</math> וגם מתקיים <math>f(|f_i (x)|)</math> אי-זוגי או <math>f_i(x) \notin SAT</math>
#<math>x \notin SAT</math> וגם <math>f(|f_i (x)|)</math> זוגי וגם <math>f_i(x) \notin SAT</math>
::אם קיים כזה x, אזי בדומה למקודם, <math>f(n+1) = f(n) + 1</math>. אחרת <math>f(n+1) = f(n)</math>.
עכשיו נסביר מדוע זה עובד.

ראשית כל נשים לב שאין קשר בין הפונקציות <math>f_i </math> לפונקציה <math>f </math>

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

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

עתה סיימנו להוכיח רעיונית שהשפה A אינה נמצאת ב-P. נרצה להוכיח שהשפה גם אינה NPC, כלומר לא קיימת רדוקציה פולינומית מ-SAT אל A.
כמו שהגדרנו מקודם, יש לנו רשימה של כל הפונקציות הפולינומיות הקיימות. אם השפה A היא אכן NPC אזי אחת מהפונקציות היא רדוקציה פולינומית מ-SAT אל A. לכן אנחנו מחפשים עבור כל פונקציה <math>f_i </math> קלט x עבורו הפונקציה לא מהווה רדוקציה ל-A (וכתוב למעלה איך עושים את זה פורמלית בדיוק). כעת נותר להוכיח שהתנאים לבסוף מתקיימים, כלומר שאין איזה i עבורו <math>f_i </math> כן מהווה רדוקציה ל-SAT. לכל פונקציה <math>f_i </math> שהיא רדוקציה ל-SAT, מההנחה ש <math>P \neq NP</math> אורך הפלט של הפונקציה <math>f_i</math> גדל, ולכן בסופו של דבר נגיע ל-<math>|f_i(x)|</math> מספיק גדול שיהיה אי-זוגי ונגרום לכך ש-<math>f_i </math> לא תהיה רדוקציה טובה.

הדרישה שאם <math>log^{f(n)}(n) \ge n</math> אז <math>f(n+1)=f(n)</math> נועדה כדי שבכל שלב נוכל להשתמש בפונקציות <math>f(|f_i(x)|)</math>
בסך הכל הוכחנו בחלק הראשון ש-A לא ב-P, ובחלק השני שאין רדוקציה פולינומית מ-SAT ל-A, ולכן הפונקציה A נמצאת ב-NPI, כדרוש.

===הוכחה עם ריפוד SAT===
נגדיר את <math>\{M_i\}_{i=1}^\infty, \{f_i\}_{i=1}^\infty </math> כמקודם.

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

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

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

#<math>M_i(x) </math> מקבל את x, אבל <math>x \notin L</math>
#<math>M_i(x) </math> דוחה את x, אבל <math>x \in L</math>

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

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

ברור שהבנייה לא נתקעת על i מסוים, מכיוון שבמקרה כזה הייתה רדוקציה טריוויאלית מ-SAT ל-L, אבל המכונות <math>M_i </math> הן פולינומיות, וזה סותר את ההנחה <math>P \neq NP</math>.

לכן מילאנו את התנאי שהשפה L אינה פולינומית. כעת נניח שיש פונקציה <math>f_j(\cdot )</math> עושה רדוקציה פולינומית מ-SAT ל-L. נרצה להראות שזה גורר ש-SAT פתירה בזמן פולינומי (וכנגד ההנחה שלנו, כמובן)

הוכחה. מאחר ש <math>f_j(x) </math> רצה לכל היותר בזמן <math>|x|^j </math>, מתקיים <math>|f_j(\phi)|\leq |\phi|^j </math>. חייב להיות <math>n_0 </math> כך שלכל <math>n \ge n_0 </math> מתקיים <math>f(n)=n^k, k > j</math>. מכיוון ש-<math>n_0 </math> קבוע, אפשר פשוט לפתור את כל הבעיות מאורך קטן או שווה לו בזמן אקספוננציאלי. 

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

==בעיות חשודות להיות ב-NPI==
===תורת המספרים ואלגברה===
*בעיית הפירוק לגורמים
*בעיית הלוג הדיסקרטי
*בעיית איזומורפיזם בין גרפים וחוגים
===תורת המשחקים===
*מציאת המנצח במשחק זוגיות
===אלגוריתמים בגרפים===
*בעיית איזומורפיזם בין גרפים
===למידת מכונה===
*מציאת מימד VC של בעיה
==לקריאה נוספת==
* Michael Sipser, Introduction to the Theory of Computation, Thompson, 1996

==הערות שוליים==

קטגוריה:מחלקות סיבוכיות