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

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

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

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

חישובית

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

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

סיבוכיות

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

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

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

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

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

דוגמה

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

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

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

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

קישורים חיצוניים

• רדוקציה חישובית, באתר MathWorld (באנגלית)