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

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