דוגמא 470350
אפשר לקבל דוגמא לבעיה שהיא *לא* NP?

תודה
דוגמא 470353
כל הבעיות ב-NP הן כריעות. לכן, בעיות שאינן כריעות הן לא NP. לכן (לדוגמא) בעיית העצירה [ויקיפדיה] היא לא ב-NP.
דוגמא 470357
זו דוגמא טריוויאלית מדי. אני רוצה בעיה *כריעה* שלא נמצאת בNP.
דוגמא 470362
באמת מעניין.

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

גדי?
דוגמא 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.

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

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

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

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

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

מה כן?

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

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

TQBF [Wikipedia] היא בעיה חביבה למדי שמאוד לא סביר שתהיה ב-NP, אבל לא באמת ידוע; היא מה שנקרא PSPACE-שלמה, שזה כמו NP-שלמה רק עבור מחלקה (כנראה) גדולה יותר, של כל הבעיות שאפשר לפתור בסיבוכיות *זכרון* פולינומית. היא די דומה באופיה ל-SAT, למי שמכיר, רק שכאן יש לנו נוסחה בתחשיב *הכמתים*. כאמור, ייתכן ש-P=PSPACE ואז בפרט זו בעיית NP; אבל זה מאוד מאוד לא סביר.

מקום טוב אחד להתחיל לחפש בו דוגמאות לבעיות קשות "ממש" הוא "אלגוריתמיקה" של דוד הראל, שלצערי לא לידי כרגע.
חרוזים 473143
אהבתי במאמר שלך
את תמונת החרוזים
חרוזים 473201
חשבונייה, קראו לזה פעם.
באנגלית זה הרבה יותר מגניב: Abacus 473239
והנה אתר שמוקדש לו: http://www.ee.ryerson.ca/~elf/abacus/
באנגלית זה הרבה יותר מגניב: Abacus 473296
בהמשך לדיון על אאופמיזם: זו לא מילה אנגלית! זו מילה לטינית, ממקור יווני עם ניחוח שמי, והיא משותפת לכל שפות אירופה. די לאנגלוצנטריות!
זו כן מילה אנגלית. 473306
פשוט מקורה בלטינית (לא כתבתי בשום מקום שזו מילה *רק* באנגלית).
זו כן מילה אנגלית. 473310
קראתי פעם שמקורה במלה ''אבק''.
הא! מסתבר שזו בכלל מילה בעברית! 473325
זאת אומרת, אם מאמינים לזה:
או שמא בפיניקית:

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

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