בתשובה לענק עדין, 05/02/08 1:21
דוגמא 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.

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

---------
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות