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