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

