משתמש:דניאל ב./משפט לדנר

בתורת הסיבוכיות, משפט לדנר הוא משפט הקובע, שתחת ההנחה ש-P≠NP, קיימות בעיות ב-NP שאינן ב-P ואינן NP-שלמות. את המשפט הוכיח ריצ'ארד לדנר ב-1975.

רקע

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

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

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

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

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

משפט לדנר קובע שאם אכן P≠NP, אז המחלקה NPI אינה ריקה וקיימות בעיות שאינן ב-P ואינן NP-שלמות. הוכחת המשפט בונה בלכסון בעיה שכזו (כמצופה מבנייה בלכסון, הבעיה שנבנת אינה "טבעית", היא לא צצה בהקשרים אחרים מחוץ להוכחת המשפט).

הוכחה

הבנייה תהיה מבוססת על השפה SAT המכילה את כל נוסחאות CNF שיש השמה המספקת אותן. משפט קוק-לוין קובע שהכרעת השפה היא בעיה NP-שלמה. נגדיר שפה:

$L=\{\phi 01^{f(n)-n-1}:|\phi |=n,\phi \in {\mbox{SAT}}\}$

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