נתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלוי…

נתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נוסחה $φ$ מצורת 3-CNF עם m הסנרים נחזיר גרף G ואת המספר m. הגרף G יונדר כלהלן. קדקודים: לכל הסנר של $φ$ יונדר בגרף אוסף של קודקודים שמתאימים לכל ההשמות המספקות שלו (למשל, עבור הסנר בגודל 3 שבו מופיעים שלושה משתנים שונים יהיו בגרף G שבעה קודקודים - אחד לכל אחת משבע השמות המספקות את ההסנר). קשתות: תהיה קשת עבור כל שני קודקודים שמתאימים להשמות אשר סותרות זו את זו (כלומר אחת מהן נותנת למשתנה מסויים ערך True והאחרת נותנת לו ערך False). שימו לב שבפרט תהיה קשת עבור כל שני קודקודים שהוספנו עבור הסנר. נתונה הנוסחה $(x1\vee x2\vee x3)\wedge(x1\vee x4)$ ונתבונן בגרף שהוא פלט הרדוקציה הנ"ל על נוסחה זו. השאלה היא מה מספר הקשתות בגרף זה.