פורטל:מדעי המחשב/תמונה נבחרת/9

דוגמה לרדוקציה פולינומית מבעיית הספיקות ‎CNF-SAT‎ לבעיית כיסוי הקודקודים
כאן הפסוק הנתון הוא $(A\lor B)\land (\lnot A\lor \lnot B\lor \lnot C)\land (\lnot A\lor B\lor C)$
וההשמה המספקת את הפסוק היא ${\Big \{}A,B',C{\Big \}}$