 |
|
 |
||
|
||||
 |
אפשר לקבל דוגמא לבעיה שהיא *לא* NP? תודה |
 |
 |
 |
|
|
|
||
|
||||
|
כל הבעיות ב-NP הן כריעות. לכן, בעיות שאינן כריעות הן לא NP. לכן (לדוגמא) בעיית העצירה [ויקיפדיה] היא לא ב-NP. | |
|
|
|
|
|
||
|
||||
|
זו דוגמא טריוויאלית מדי. אני רוצה בעיה *כריעה* שלא נמצאת בNP. | |
|
|
|
|
|
||
|
||||
|
באמת מעניין. כל חומר הקריאה שלי בנושא חוזר ומזכיר שיש כאלה (בעיות ספירה?), אבל הטקסט מציין כדרך אגב ש"נהוג להאמין שהבעיה לא ב-NP" או "סביר להניח שאיננה ב-NP" או ש"ההוכחה לכך שבעיה זו איננה ב-NP איננה פשוטה". גדי? |
|
|
|
|
|
|
||
|
||||
|
ידוע שהמחלקה EXSPACE (בעיות שניתן לפתור עם מכונת טיורינג עם מקום אקספוננציאלי באורך הקלט) מכילה ממש את NP. לכן בעיות שלמות ב-EXSPACE אינן ב-NP. לדוגמאות לבעיות כנ"ל ראה http://en.wikipedia.org/wiki/EXPSPACE |
|
|
|
|
|
|
||
|
||||
|
ב-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. ואני עצמי לא מסוגל (כרגע) להסביר יותר מכך.--------- |
|
|
|
|
|
|
||
|
||||
|
מה בדבר בעיית ההכרעה "לגרף הנתון אין מעגל המילטוני"? זו בוודאי בעייה ב-co-NP כי אם אין זה נכון שאין בגרף מעגל המילטוני, יש לכך הוכחה פשוטה (הנה המעגל). מצד שני, לא נראה שיש בהכרח "עד" פולינומיאלי לכך שגרף נתון *אינו* מכיל מעגל כזה. מצד שלישי, הוכחה לכך שבעייה זו באמת איננה ב-NP תהווה גם הוכחה לכך ש-NP שונה מ-co-NP, ואם אינני טועה(?) זו בעייה פתוחה הנחשבת קשה. נדמה לי שלפנינו בעייה כריעה שאיננה ב-NP (כפי שביקשת), אך איננו יודעים להוכיח שזה באמת המצב. |
|
|
|
|
|
|
||
|
||||
|
א) למעשה הבעיה הנ"ל היא co-NP שלמה, דהיינו היא (1) ב-co-NP כפי שאמרת ו-(2) היא "קשה" לפחות כמו כל בעיה ב- co-NP. על כן, לא זו בלבד שהוכחת ההשערה הנ"ל ("אין-מעגל-המילטוני אינה ב-NP") מספיקה כדי להוכיח את הטענה "NP שונה מ-co-NP ", היא גם הכרחית, כלומר, שתי הטענות הן שקולות. ב) אינך טועה זוהי בעיה פתוחה חשובה ומפורסמת, ועל פי מצב הידע הנוכחי, נראה שאנו רחוקים שנות אור מלגרד את קצה אפה של טענה כזו. |
|
|
|
|
|
|
||
|
||||
|
אני לא מכיר דוגמא "מעניינת" (אולי כי בעיה כזו הייתה כבר נזנחת מזמן). מה כן? בעיית מגדלי האנוי מובאת תמיד בתור דוגמה לבעיה שהפתרון שלה (רשימת הצעדים שצריך לבצע כדי לפתור את המגדל) יהיה אקספוננציאלי בהכרח. כמובן שזה "לא מעניין" כי כאן ידוע בדיוק איך לפתור ורק ביצוע הפתרון עצמו הוא אקספוננציאלי. יש מה שנקרא "משפטי היררכייה" לסיבוכיות שמבטיחים קיום בעיה שאפשר לפתור רק בסיבוכיות (זמן/זכרון) גדולה כרצוננו, כל עוד הפונקציה היא "נורמלית" (2 בחזקת n זו פונקציה נורמלית, לצרכנו). ההוכחה היא בשיטת לכסון ובאופן כללי לא נותנת ביד שום בעיה ידועה ומעניינת. TQBF [Wikipedia] היא בעיה חביבה למדי שמאוד לא סביר שתהיה ב-NP, אבל לא באמת ידוע; היא מה שנקרא PSPACE-שלמה, שזה כמו NP-שלמה רק עבור מחלקה (כנראה) גדולה יותר, של כל הבעיות שאפשר לפתור בסיבוכיות *זכרון* פולינומית. היא די דומה באופיה ל-SAT, למי שמכיר, רק שכאן יש לנו נוסחה בתחשיב *הכמתים*. כאמור, ייתכן ש-P=PSPACE ואז בפרט זו בעיית NP; אבל זה מאוד מאוד לא סביר. מקום טוב אחד להתחיל לחפש בו דוגמאות לבעיות קשות "ממש" הוא "אלגוריתמיקה" של דוד הראל, שלצערי לא לידי כרגע. |
|
|
|
|
|
|
||
|
||||
|
אהבתי במאמר שלך את תמונת החרוזים |
|
|
|
|
|
|
||
|
||||
|
חשבונייה, קראו לזה פעם. | |
|
|
|
|
|
||
|
||||
|
והנה אתר שמוקדש לו: http://www.ee.ryerson.ca/~elf/abacus/ | |
|
|
|
|
|
||
|
||||
|
בהמשך לדיון על אאופמיזם: זו לא מילה אנגלית! זו מילה לטינית, ממקור יווני עם ניחוח שמי, והיא משותפת לכל שפות אירופה. די לאנגלוצנטריות! | |
|
|
|
|
|
||
|
||||
|
פשוט מקורה בלטינית (לא כתבתי בשום מקום שזו מילה *רק* באנגלית). | |
|
|
|
|
|
||
|
||||
|
קראתי פעם שמקורה במלה ''אבק''. | |
|
|
|
|
|
||
|
||||
|
זאת אומרת, אם מאמינים לזה: או שמא בפיניקית: |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |