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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

[עריכה] ראו גם

שפות אחרות