בתשובה לענק עדין, 05/02/08 1:21
 |
|
 |
||
|
||||
 |
מה בדבר בעיית ההכרעה "לגרף הנתון אין מעגל המילטוני"? זו בוודאי בעייה ב-co-NP כי אם אין זה נכון שאין בגרף מעגל המילטוני, יש לכך הוכחה פשוטה (הנה המעגל). מצד שני, לא נראה שיש בהכרח "עד" פולינומיאלי לכך שגרף נתון *אינו* מכיל מעגל כזה. מצד שלישי, הוכחה לכך שבעייה זו באמת איננה ב-NP תהווה גם הוכחה לכך ש-NP שונה מ-co-NP, ואם אינני טועה(?) זו בעייה פתוחה הנחשבת קשה. נדמה לי שלפנינו בעייה כריעה שאיננה ב-NP (כפי שביקשת), אך איננו יודעים להוכיח שזה באמת המצב. |
 |
 |
 |
|
|
|
||
|
||||
|
א) למעשה הבעיה הנ"ל היא co-NP שלמה, דהיינו היא (1) ב-co-NP כפי שאמרת ו-(2) היא "קשה" לפחות כמו כל בעיה ב- co-NP. על כן, לא זו בלבד שהוכחת ההשערה הנ"ל ("אין-מעגל-המילטוני אינה ב-NP") מספיקה כדי להוכיח את הטענה "NP שונה מ-co-NP ", היא גם הכרחית, כלומר, שתי הטענות הן שקולות. ב) אינך טועה זוהי בעיה פתוחה חשובה ומפורסמת, ועל פי מצב הידע הנוכחי, נראה שאנו רחוקים שנות אור מלגרד את קצה אפה של טענה כזו. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |