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

מתוך testwiki

גרסה מ־03:20, 21 בדצמבר 2010 מאת imported>Gran (טוב, בגלל הפסוקית הראשונה לא מדובר ב3-sat. הכי קרוב זה cnf-sat.)

(הבדל) → הגרסה הקודמת | הגרסה האחרונה (הבדל) | הגרסה הבאה ← (הבדל)

קפיצה לניווט קפיצה לחיפוש

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

אוחזר מתוך "https://he.wiki.beta.math.wmflabs.org/w/index.php?title=פורטל:מדעי_המחשב/תמונה_נבחרת/9&oldid=3034"