Question

classification_p_np
vertex_cover

בהנחה ש-PNPP \neq NP קבעו האם השפה הבאה היא ב-PP או לא. הוכיחו את תשובתכם.

}\}הגרף G=(AB,E)G = (A \cup B, E) הוא דו צדדי וקיימת DBD \subseteq B בגודל kk, כך שהגרף המושרה G[AD]G[A \cup D] קשיר L4={(A,B,E),k:L_4 = \{(A, B, E),k :

1

Answers

נראה שהשפה לא ב-P על ידי רדוקציה מ-VC:

f(G=(V,E),k)=G=(E{x},V,E),kf(G = (V, E), k) = G' = (E \cup \{x\}, V, E'), k

כאשר

E={(v,x)}vV{(e,v):eEve}E' = \{(v, x)\}_{v \in V} \cup \{(e, v) : e \in E \land v \in e\}

למשל עבור הגרף הבא:

יתקבל הגרף הדו צדדי הבא:

נשים לב שאם CVC \subseteq V כיסוי בצמתים ב-GG בגודל kk אז הגרף G[E{x}C]G'[E \cup \{x\} \cup C] קשיר וזאת מכיוון שלכל צומת ב-EE יש שכן ב-CC ו-xx שכן של כל הצמתים ב-CC.

מצד שאני אם DVD \subseteq V כך ש-G[E{x}D]G[E \cup \{x\} \cup D] קשיר, אז לכל צומת ב-EE חייב להיות שכן ב-DD וזה קורה רק אם DD כיסוי ב-GG.

1
Feedback