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

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