רדוקציה חישובית

רדוקציה היא שיטה אלגוריתמית שממירה בעיה אחת לבעיה אחרת שעוזרת לפתור אותה. לדוגמה, אם יודעים לפתור בקלות את הבעיה "מהו המספר הראשון בסדרה", אפשר למצוא את המספר הקטן ביותר על ידי מיון הסדרה ואז שימוש בפתרון של הבעיה הראשונה.

באופן פורמלי רדוקציה מ-A ל-B היא פונקציה f שממירה קלט x של A לקלט f(x) של B כך ש-A(x)=B(f(x)). מסמנים זאת כ-A≤B. קיימות רדוקציות מסוג מיפוי (≤_m) ורדוקציות פולינומיות (≤_p), שהן מקרה מיוחד של מיפוי.

רדוקציות משמשות להוכחות לגבי כריעות (האם בעיה ניתנת להכרעה או לא). מפעילים רדוקציה מבעיה ידועה כדי להראות שקשה או בלתי כריע לפתור בעיה אחרת. למשל, משפט רייס משתמש ברדוקציה מבעיית העצירה כדי להראות שתכונות מסוימות של פונקציות אינן כריעות.

בתחום הסיבוכיות מתעניינים בשאיפה למדוד משאבים כמו זמן וזיכרון. רדוקציה מאפשרת להשוות בעיות: אם יודעים את סיבוכיותה של בעיה B, אז רדוקציה מ-A ל-B נותנת הערכה לסיבוכיות של A. חשוב שהפונקציה שמבצעת את הרדוקציה לא תצרוך משאבים משמעותיים ביחס לבעיות עצמן.

רדוקציה פולינומית היא רדוקציה שחישובה לוקח זמן פולינומי ביחס לאורך הקלט. זמן ריצה פולינומי נחשב יעיל, לכן רדוקציות כאלה משמשות להראות שקיום פתרון יעיל לבעיה אחת ייתן פתרון יעיל לבעיה אחרת. בעיות שממובן שפתרון יעיל שלהן יפתור את כל מחלקת NP נקראות NP-קשות.

בעיה: נתון גרף מכוון וממושקל (גרף הוא אוסף קודקודים וקשתות), עם קודקוד התחלה וקודקוד סיום; חלק הקודקודים כחולים וחלקם אדומים. יש למצוא מסלול המינימלי שעובר בלכל היותר קודקוד אדום אחד.
פתרון דרך רדוקציה: בונים גרף חדש G' שמעתיק את G. ב-G מוחקים קשתות שיוצאות מקודקודים אדומים. ב-G' מוחקים קשתות שנכנסות לקודקודים אדומים. מוסיפים מכל קודקוד אדום v, ומקודקוד ההתחלה והסיום, קשת במשקל 0 אל העתקו 'v ב-G'. באחרון מחפשים מסלול קצר ביותר בעזרת אלגוריתם קיים. אם המסלול עובר דרך צלע שמחברת w ל-'w אז מוחקים צלע זו ומסירים את הסימונים "'" מהקודקודים אחרי 'w. המסלול המתקבל הוא פתרון לבעיה המקורית.

רדוקציה היא דרך להחליף בעיה בבעיה אחרת שעוזרת לפתור אותה. לדוגמה, כדי למצוא את המספר הקטן ביותר בסדרה, אפשר למיין את המספרים ואז לקחת את הראשון.

רדוקציה עוזרת להראות אם בעיה ניתנת לפתרון או לא. משתמשים בה כדי לקשר בעיות שקשה לפתור.

רדוקציה פולינומית היא רדוקציה שחישוב שלה יעיל. אם יש פתרון יעיל לבעיה אחת, אפשר לקבל פתרון יעיל גם לבעיה אחרת.

בעיה: יש גרף. גרף הוא נקודות (קודקודים) וקווים שמקשרים ביניהן (קשתות). יש נקודות כחולות ונקודות אדומות. רוצים את המסלול הקצר ביותר שעובר ביותר מקודקוד אדום אחד.
איך מפעילים רדוקציה: עושים העתק של הגרף. במקור מוחקים קווים שיוצאים מתוך נקודות אדומות. בהעתק מוחקים קווים שנכנסים לנקודות אדומות. מחברים כל נקודה אדומה ונקודות התחלה וסיום להעתק שלה בקו באורך 0. מחפשים את המסלול הקצר בגרף החדש. לאחר מכן מתקנים את המסלול כדי לקבל מסלול חוקי בגרף המקורי.