תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
מ ←‏הגדרה: הגהה, קישורים פנימיים
Atavory (שיחה | תרומות)
שורה 7:
==דוגמה לרדוקציה ומאפייניה==
 
נניח שנתנת לנו הבעיה הבאה: נתונה רשימת מספרים, ועלינו למצוא האם האיבר הגדול ביותר מופיע לפחות שלוש פעמים. כמובן שאפשר לפתור זאת בדרכים שונות. עם זאת, נניח שעומדת ברשותנו שגרה המקבלת רשימת מספרים, ומוצאת האם האיבר ה''קטן'' ביותר מופיע ''פחות''לפחות משלוששלוש פעמים. האם נוכל להשתמש בשגרה זו? בודאי. נוכל לעשות זאת באופן הבא:
# נקח את הרשימה המקורית, ונמיר אותה לרשימת המספרים ההפוכים בסימניהם לרשימה המקורית (לדוגמה, הרשימה <math>[1, -3, 4, 2]</math> תהפוך לרשימה <math>[-1, 3,-4, -2]</math>).
# נפעיל את השגרה שכבר קיימת לנו, ונקבלונחזיר את תוצאתה.
# נחזיר את ההיפך מהתוצאה שהתקבלה.
 
קל לראות ששיטה זו פותרת את הבעיה החדשה. אמ"ם האיבר הקטן ביותר ברשימה החדשה, נסמנו כ
<math>-y</math>
מופיע פחותלפחות משלוששלוש פעמים ברשימה החדשה, אז לא נכון שהמספרהמספר הגדול ביותר ברשימה המקורית, y, מופיע לפחות שלוש פעמים ברשימה המקורית.
 
אפשר לראות שהמרנו בעיה חדשה לבעיה קודמת, לגביה אנו יודעים יותר (במקרה זה, יש כבר שגרה כתובה לה), באופן שמועיל לפתרון. מה מאפיין המרה זו?