למי ששאל בקשר לEXP=NEXP

[N1ce guy]

מחלקות סיבוכיות

מישהו יכול להסביר לי למה P=NP גורר EXP=NEXP ? תודה מראש.

 

[N1ce guy]

אגב,

במקור זה היה הפוך... EXP!=NEXP גורר P!=NP אולי זה יהיה יותר נוח להסביר את הגרסא הזאת.

 

[N1ce guy]

אף אחד לא יודע?

:-\

 

[N1ce guy]

ממ

*

 

[shirbi]

מה זה המחלקות הללו?

EXP, NEXP?

 

[N1ce guy]

הממ

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

 

[the new L]

נצל"ש סיבוכיות

רציתי לנצל את השרשור בשביל להלל את איש הסיבוכיות הגדול, זוכה פרס טיורינג, מנואל בלום

 

[the new L]

מקפיץ

למקרה שמישהו עוד לא קרא על מנואל בלום

 

[johnny d]

פשוט מאוד

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

 

[N1ce guy]

הבנתי בערך.

אבל איך השתמשת בזה ש- P=NP?

 

[johnny d]

המממ...

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

 

[N1ce guy]

אוקיי, תודה

 

[ron369]

"מכאן ניתן להסיק"

זה לא מדוייק במיוחד. אתה בטוח שזה באמת כ"כ פשוט?

 

[johnny d]

זה ממש לא פשוט

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

 

[johnny d]

זה כן פשוט

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

 

[johnny d]

למי ששאל בקשר לEXP=NEXP

ההודעה הקודמת לא רוצה לקפוץ לה... שם הרדוקציה מבעיה לא דטרמיניסטית לבעיה דטרמיניסטית במחלקות סיבוכיות מעל מכונה קלאסית כלשהי (כלומר לדוגמה מכונת טיורינג) הוא reachability method. הטוען כי כל חישוב בסיבוכיות מקום לא דטרמיניסטי יכול להתבצע בסיבוכיות זמן דטרמיניסטית אקספוננציאלית ע"י רדוקציה פשוטה. בעזרת רדוקציה זו בדיוק ניתן להראות את הטענה המבילה לסיבוכיות מקום לא דטרמיניסטית אקספוננציאלית. הטענה P=NP, מעידה בין השאר על שיוויון קרדינלי של בעיות שלמות במחלקה ולכן קיימת רדוקציה לוגריתמית מ-זמן לא דטרמיניסטי לזמן דטרמיניסתי. מכאן מיד ניתן להכליל את התוצאות הקודמות ע"י החלפת פרמטרים לתוצאה כי EXP = NEXP. הטענות הטריויאליות שדילגתי עליהן זה שסיבוכיות זמן X מעידה מיד על סיבוכיות מקום לא יותר מ-X, ולהיפך סיבוכיות זמן X מעידה על סיבוכיות מקום שהיא מקסימום X.

 

[ציפור ססגונית]

ריפוד

תשתמש בריפוד. בקצרה: תיקח שפה ב NEXP, תרפד אותה ע"י הוספת מס' אקס' של אפסים, תראה שהשפה החדשה ב NP, ולכן ב P ומכאן תסיק שהשפה המקורית ב EXP.