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 \ge 1 נגדיר את f(n+1):

אם log^{f(n)}(n) \ge 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 גדל, ולכן בסופו של דבר נגיע ל-|f_i(x)| מספיק גדול שיהיה אי-זוגי ונגרום לכך ש-f_i  לא תהיה רדוקציה טובה.

הדרישה שאם log^{f(n)}(n) \ge n אז f(n+1)=f(n) נועדה כדי שבכל שלב נוכל להשתמש בפונקציות f(|f_i(x)|)
בסך הכל הוכחנו בחלק הראשון ש-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 . חייב להיות n_0  כך שלכל n \ge n_0  מתקיים f(n)=n^k, k > j. מכיוון ש-n_0  קבוע, אפשר פשוט לפתור את כל הבעיות מאורך קטן או שווה לו בזמן אקספוננציאלי. 

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

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

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

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