Question

reduction_p_np
3col

פסוק 2CNF2CNF_{\neq} זהה לפסוק 2CNF2CNF פרט לאופן שבו מוגדרים ליטרלים והשמה:

  • כל ליטרל בפסוק הוא מהצורה xibx_i \neq b כאשר b{1,2,3}b \in \{1, 2, 3\}
  • השמה היא פונקציה f:V{1,2,3}f:V \to \{1, 2, 3\} כלומר נותנת לכל משתנה ערך בן 1 ל 3.
  • ערך של ליטרל xibx_i \neq b הוא TT אם f(xi)bf(x_i) \neq b

דוגמה:

הפסוק הבא ספיק עבור ההשמה f(x1)=f(x2)=2f(x_1) = f(x_2) = 2:

(x11x22)(x12x21) (x_1 \neq 1 \lor x_2 \neq 2) \land (x_1 \neq 2 \lor x2 \neq 1)
  • הוכיחו: השפה הבאה היא NPCNPC

}\}הפסוק φ\varphi הוא פסוק 2CNF2CNF_{\neq} ספיקL1={φ:L_1 = \{\varphi :

הדרכה: קיימת רדוקציה מ-3COL3COL.

1

Answers

נראה רדוקציה מ-3COL:

בהינתן גרף (בלי צמתים מבודדים בה"ק), G=(V,E)G = (V, E), נייצר את הפסוק הבא:

φ=uvE(xu̸=1xv̸=1)(xu̸=2xv̸=2)(xu̸=3xv̸=3) \varphi = \bigwedge_{uv \in E} (x_u \neq 1 \lor x_v \neq 1) \land (x_u \neq 2 \lor x_v \neq 2) \land (x_u \neq 3 \lor x_v \neq 3)

נניח כי c:V{1,2,3}c:V \to \{1, 2, 3\} צביעה חוקית של GG ונגדיר את ההשמה f(xv)=c(v)f(x_v) = c(v). נניח בשלילה ש-ff אינה מספקת, כלומר, קיימת קשת uvuv ופסוקית (xu̸=bxv̸=b)(x_u \neq b \lor x_v \neq b) שלא סופקה, ומכאן ש-c(u)=c(v)=bc(u) = c(v) = b - סתירה.

נניח ש-ff השמה מספקת לפסוק ונגדיר צביעה c(v)=f(xv)c(v) = f(x_v). נניח בשלילה ש-cc אינה צביעה חוקית, כלומר קיימת קשת uvuv כך (בה"ק) ש-c(u)=c(v)=1c(u) = c(v) = 1, כלומר f(xu̸=1xv̸=1)=Ff(x_u \neq 1 \lor x_v \neq 1) = F - סתירה.

כלומר φL1    G3COL\varphi \in L_1 \iff G \in \text{3COL}.

קל לראות שהרדוקציה ניתנת לחישוב בזמן פולינומי.

2
Feedback