בתשובה להאייל האלמוני, 19/01/08 0:36
 |
|
 |
||
|
||||
 |
אתה בהחלט צודק - זו אכן המשמעות של כך. אני לא מכיר בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט ועם זאת פתרון שלהן ניתן לבדיקה פולינומית. מכיוון ש"בצע רדוקציה ל-SAT ובדוק את כל ההצבות) הוא פתרון נאיבי למדי (במובן זה שאין בו שום דבר מחוכם מעבר לקופסה השחורה של הרדוקציה), קח בחשבון ש"הפתרון הרגיל" מוגדר בהתאם. |
 |
 |
 |
|
|
|
||
|
||||
|
אפשר גם לומר שכיוון שלפי ההגדרה לכל בעיה ב- NP יש הוכחה באורך פולינומי שאפשר לבדוק בזמן פולינומי, אפשר פשוט לבדוק את כל המחרוזות באורך המתאים ולראות אם הן מהוות הוכחה וזה ייתן פתרון בזמן אקספוננציאלי (כשהמעריך הוא פולינום באורך הקלט). לא ידוע (וכנראה שלא נכון) שכל בעיה ב- NP ניתנת לפתרון בזמן אקספוננציאלי עם מעריך ליניארי באורך הקלט. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |