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

הרדוקציה היא כזו: בהינתן פסוק בתחשיב הפסוקים, בדוק (בזמן אקספוננציאלי, בצורה הנאיבית) אם הוא ספיק. אם כן, העתק אותו ל-‏1. אם לא, העתק אותו ל-‏0.

מה קיבלנו? שפסוק הוא ספיק אם ורק אם הוא מועתק ל-x שעליו האלגוריתם שפותר את הבעיה הפשוטה עונה "כן".

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים