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

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

באופן פורמלי ניתן לומר כי רדוקציה מפונקציה A לפונקציה B היא פונקציה f מלאה וניתנת לחישוב מקבוצת הקלטים האפשריים של A לקבוצת הקלטים האפשריים של B, כך שלכל x מתקיים: $\ A(x)=B(f(x))$.

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

חישובית

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

סיבוכיות

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

רדוקציה פולינומית

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

דוגמה

בעיה: בהינתן G גרף מכוון וממושקל, עם קודקוד התחלה וקודקוד סיום, אשר חלק מקודקודיו צבועים בצבע כחול והשאר באדום, עלינו למצוא את המסלול הקצר ביותר אשר עובר בלכל היותר קודקוד אדום אחד.

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

את הגרף החדש ניצור באופן הבא: ניצור גרף חדש 'G, אשר זהה לחלוטין לגרף G. כעת, נוריד מגרף G כל צלע אשר יוצאת מקודקוד אדום, ונוריד מגרף 'G כל צלע הנכנסת לקודקוד אדום. כעת, מכל קודקוד אדום v אשר בגרף G, וכן מקודקוד ההתחלה ומקודקוד הסיום, נוציא צלע מכוונת אל קודקוד 'v בגרף 'G, שמשקלה יהיה 0. כעת, נחפש אחר המסלול הקצר ביותר בגרף החדש שקיבלנו.

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

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