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