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