NP ביניים

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

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

משפט לדנרעריכה

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

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

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

תהיינה   כל המכונות הפולינומיות אשר רצות לכל היותר בזמן   כל אחת, ותהיינה באופן דומה   כל הפונקציות הפולינומיות שרצות בזמן לכל היותר  . נשים לב שכל המכונות הפולינומיות וכל הפונקציות הפולינומיות נמצאות כאן.

נגדיר שפה -

 

ברור שאם הפונקציה f חשיבה בזמן פולינומי אזי  .

נגדיר את הפונקציה f כך:  . עבור   נגדיר את  :

אם   אז נשאיר את  

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

  •   (כלומר ערך זוגי), נבדוק האם קיים קלט x,   כך ש-
  1.   מקבלת את x וגם   אי-זוגי או  , או
  2.   דוחה את x וגם   זוגי או  
אם קיים כזה x, אזי  . אחרת  .
  •   (כלומר ערך אי זוגי), נבדוק האם קיים קלט x,   כך ש-
  1.   וגם מתקיים   אי-זוגי או  
  2.   וגם   זוגי וגם  
אם קיים כזה x, אזי בדומה למקודם,  . אחרת  .

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

ראשית כל נשים לב שאין קשר בין הפונקציות   לפונקציה  

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

באופן אנלוגי נותנים את התנאי השני. אם המכונה לא מקבלת את x אבל x כן ב-SAT, אז מצאנו שוב x שהמכונה   נכשלת עליו. אחרי שהבנו איך הבניה מפרידה את SAT מכל מכונה פולינומית, נסביר בקצרה את העניין עם הפונקציה  . השימוש בפונקציה הזו נועד כדי שנוכל לסנן עוד מילים מהשפה, כדי שהיא לא תהיה NPC (שלמה). לכן בכל תנאי, במקום לדרוש המילה תהיה או לא תהיה ב-SAT, אנחנו דורשים שהמילה תהיה או לא תהיה ב-A, כלומר מוסיפים את הדרישה ש-  זוגי. ברור שנמצא x כזה, כי הנחנו ש- , אז אין לכל מכונה פולינומית יש קלט x עבורו היא מחזירה תשובה לא נכונה.

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


הדרישה שאם   אז   נועדה כדי שבכל שלב נוכל להשתמש בפונקציות  [3] בסך הכל הוכחנו בחלק הראשון ש-A לא ב-P, ובחלק השני שאין רדוקציה פולינומית מ-SAT ל-A, ולכן הפונקציה A נמצאת ב-NPI, כדרוש.

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

נגדיר את   כמקודם.

נגדיר שפה  

אנחנו נשאיר את   עד שנקיים את התנאי ה-i, ואז נקדם את   להיות  

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

  1.   מקבל את x, אבל  
  2.   דוחה את x, אבל  

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

מכיוון שאנחנו בודקים רק עבור   ניתן לחשב את f בזמן פולינומי

ברור שהבנייה לא נתקעת על i מסוים, מכיוון שבמקרה כזה הייתה רדוקציה טריוויאלית מ-SAT ל-L, אבל המכונות   הן פולינומיות, וזה סותר את ההנחה  .

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

הוכחה. מאחר ש   רצה לכל היותר בזמן  , מתקיים  [4]. חייב להיות   כך שלכל   מתקיים  . מכיוון ש-  קבוע, אפשר פשוט לפתור את כל הבעיות מאורך קטן או שווה לו בזמן אקספוננציאלי.

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

בעיות חשודות להיות ב-NPIעריכה

תורת המספרים ואלגברהעריכה

  • בעיית הפירוק לגורמים
  • בעיית הלוג הדיסקרטי
  • בעיית איזומורפיזם בין גרפים וחוגים

תורת המשחקיםעריכה

אלגוריתמים בגרפיםעריכה

  • בעיית איזומורפיזם בין גרפים

למידת מכונהעריכה

לקריאה נוספתעריכה

  • Michael Sipser, Introduction to the Theory of Computation, Thompson, 1996

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

  1. ^ אם היה נשאר קבוע אז היה פותר את SAT בזמן פולינומי
  2. ^ לא הגדלנו את הפונקציה כל הזמן הזה
  3. ^ הפלט של   הוא לכל היותר באורך  , ומדרך הפעולה ברור ש- 
  4. ^ מכיוון שאי אפשר לכתוב אורך יותר מהזמן המוקצב למכונה שמחשבת את הפונקציה