Question

misc
vertex_cover

נאמר כי לשפה LL יש רדוקציה kk-עצמית מקצרת אם קיימת פונקציה ff המקיימת:

  1. הפונקציה ff ניתנת לחישוב בזמן פולינומי.
  2. קיים NN כך שלכל קלט xx שאורכו לפחות NN, f(x)=y1,y2,,ykf(x) = y_1,y_2, \ldots ,y_k (כלומר הפונקציה ff מחזירה מחרוזת שמורכבת מ kk תתי מחרוזות) כך ש:
    • מתקיים ש-yi<x|y_i| < |x| לכל 1ik1 \leq i \leq k.
    • xLx \in L     \iffקיים ii כך ש-yiLy_i \in L.

ענו על הסעיפים הבאים:

  1. הוכיחו כי אם לשפה LL יש רדוקציה 1-עצמית מקצרת, אז LPL \in P.
  2. הוכיחו כי אם לשפה LL יש רדוקציה 2-עצמית מקצרת, אז LNPL \in NP.
  3. הוכיחו: לשפה VC יש רדוקציה 2-עצמית מקצרת.
1

Answers

1. נראה אלגוריתם פולינומי שמכריע את LL. ראשית נשים לב ש-LN={x:xLxN}L_N = \{x : x \in L \land |x| \leq N\} שפה סופית ולכן ניתן להכריע אותה בזמן קבוע. אם x>N|x| > N אז ניתן לחשב (xN|x| - N פעמים) את f(f(f(x)))=xf(f(\ldots f(x))) = x' כך ש-xLNxLx' \in L_N \iff x \in L.

2. נתאר מ"ט א"ד, MM, מתאימה:

המ"ט MM על קלט xx:

  • אם xN|x| \leq N מכריעה אם xLNx \in L_N בזמן קבוע.
  • אחרת מחשבת את f(x)=y1,y2f(x) = y_1, y_2
  • מנחשת y{y1,y2}y \in \{y_1, y_2\}
  • ממשיכה באופן רקורסיבי על yy.

קל לראות ש-yLy \in L אמ"מ קיים ל-MM מסלול מקבל.

3. נגדיר f(G=(V,E),k)=(Gu,k1),(Gv,k1)f(G = (V, E), k) = (G_u, k - 1), (G_v, k - 1)

כאשר uvEuv \in E ו-Gw[V{w}]G_w[V \setminus \{w\}].

הנכונות נובעת מכך שלכל קשת uvuv ב-GG אחד הקצוות חייב להיות בכיסוי.

1
Feedback