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

קובץ:3SAT reduced too VC.svg

דוגמה לרדוקציה פולינומית מבעיית הספיקות ‎CNF-SAT‎ לבעיית כיסוי הקודקודים
כאן הפסוק הנתון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A \lor B) \land (\lnot A \lor \lnot B \lor \lnot C) \land (\lnot A \lor B \lor C)}
וההשמה המספקת את הפסוק היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Big\{ A, B', C \Big\}}