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