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

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

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

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

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

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

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

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

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

צפיות

כלים אישיים

חיפוש

ניווט

קהילה

תיבת כלים

שפות אחרות