רדוקציה מ-3SAT לקבוצה בלתי־תלויה

בניית גרף הופעות והוכחת שני כיווני הנכונות.

שאלה

בהינתן נוסחת 3CNF, $\varphi=C_1\land\cdots\land C_m$, בנו בזמן פולינומיאלי גרף $G$ כך ש-$\varphi$ ספיקה אם ורק אם ב-$G$ יש קבוצה בלתי־תלויה בגודל $m$.

רמז 1

צרו קודקוד לכל הופעת ליטרל, ולא רק לכל משתנה.

רמז 2

מנעו שתי בחירות לא תואמות: שתי הופעות מאותה פסוקית, וליטרלים משלימים מפסוקיות שונות.

פתרון מלא

לכל הופעת ליטרל בכל פסוקית יוצרים קודקוד. מחברים כל זוג קודקודים מאותה פסוקית, וכן כל שני קודקודים המסומנים $x$ ו-$\neg x$. קובעים $k=m$.

אם $\varphi$ ספיקה, בוחרים מכל פסוקית הופעה אמיתית אחת. אין שתי בחירות מאותה פסוקית ואין ליטרלים משלימים תחת השמה אחת, ולכן התקבלה קבוצה בלתי־תלויה בגודל $m$.

בכיוון ההפוך, קבוצה בלתי־תלויה בגודל $m$ כוללת לכל היותר קודקוד אחד מכל קליקת פסוקית, ולכן בדיוק אחד מכל פסוקית. אין בה זוג משלים. משייכים אמת לליטרלים החיוביים שנבחרו ושקר למשתנים שהליטרלים השליליים שלהם נבחרו, ומשלימים שרירותית. כל פסוקית מסופקת.

יש $3m$ קודקודים ולכל היותר $O(m^2)$ צלעות, ולכן הבנייה פולינומיאלית.

נקודת בדיקה

בכיוון ההפוך יש להסביר גם מדוע נבחר ליטרל מכל פסוקית וגם מדוע הבחירות עקביות.

הערת מקור

זהו ניסוח עצמאי של רדוקציה סטנדרטית. עבודות סטודנטים אינן משמשות מקור סמכות.

טעויות נפוצות

• השמטת כיוון בהוכחת הנכונות או מקרה קצה בקלט.
• מדידת משאבים לפי ערך מספרי במקום אורך הקידוד.
• החלפת הוכחת החסם באינטואיציה בלבד.

מקורות ואימות

• Merged summary, pp. 55-57
• 2026 transcript 14 (graph-reduction context)
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT20
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

פתיחה בגלריית ההמחשות: 3SAT → קבוצה בלתי תלויה