בתשובה לאביב י., 05/02/08 2:47
דוגמא 471086
ידוע שהמחלקה EXSPACE (בעיות שניתן לפתור עם מכונת טיורינג עם מקום אקספוננציאלי באורך הקלט) מכילה ממש את NP. לכן בעיות שלמות ב-EXSPACE אינן ב-NP.
לדוגמאות לבעיות כנ"ל ראה http://en.wikipedia.org/wiki/EXPSPACE
דוגמא 471090
ב-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.

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

---------

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים