בתשובה לאביב י., 05/02/08 0:48
דוגמא 470357
ענק עדין • בתשובה לאביב י. יום ג', 5/2/2008, 1:21
זו דוגמא טריוויאלית מדי. אני רוצה בעיה *כריעה* שלא נמצאת בNP.
דוגמא 470362
אביב י. • בתשובה לענק עדין יום ג', 5/2/2008, 2:47
באמת מעניין.

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

גדי?
דוגמא 471086
האייל האלמוני • בתשובה לאביב י. יום א', 10/2/2008, 8:39
ידוע שהמחלקה EXSPACE (בעיות שניתן לפתור עם מכונת טיורינג עם מקום אקספוננציאלי באורך הקלט) מכילה ממש את NP. לכן בעיות שלמות ב-EXSPACE אינן ב-NP.
לדוגמאות לבעיות כנ"ל ראה http://en.wikipedia.org/wiki/EXPSPACE
דוגמא 471090
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום א', 10/2/2008, 9:25
ב-Complexity zoo ‏1 אפילו כותבים דוגמה קונקרטית:

"The theory of reals with addition (see EXPSPACE) is hard for NEXP"

ההפניה שהם נותנים היא ל:

M. J. Fischer and M. O. Rabin. Super-exponential complexity of Presburger arithmetic, Complexity of Computation (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974.

ואני עצמי לא מסוגל (כרגע) להסביר יותר מכך.

---------
השערה 470363
אלון עמית • בתשובה לענק עדין יום ג', 5/2/2008, 4:43
מה בדבר בעיית ההכרעה "לגרף הנתון אין מעגל המילטוני"? זו בוודאי בעייה ב-co-NP כי אם אין זה נכון שאין בגרף מעגל המילטוני, יש לכך הוכחה פשוטה (הנה המעגל). מצד שני, לא נראה שיש בהכרח "עד" פולינומיאלי לכך שגרף נתון *אינו* מכיל מעגל כזה.

מצד שלישי, הוכחה לכך שבעייה זו באמת איננה ב-NP תהווה גם הוכחה לכך ש-NP שונה מ-co-NP, ואם אינני טועה(?) זו בעייה פתוחה הנחשבת קשה. נדמה לי שלפנינו בעייה כריעה שאיננה ב-NP (כפי שביקשת), אך איננו יודעים להוכיח שזה באמת המצב.
השערה 470988
צפנת פענח • בתשובה לאלון עמית שבת, 9/2/2008, 5:10
א) למעשה הבעיה הנ"ל היא co-NP שלמה, דהיינו היא (1) ב-co-NP כפי שאמרת ו-(2) היא "קשה" לפחות כמו כל בעיה ב- co-NP.

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

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