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