Question

spring_18_a
misc

נאמר ששפה LL ניתנת לבחירה אם קיימת עבורה פונקציית בחירה f:Σ×ΣΣf:\Sigma^* \times \Sigma^* \to \Sigma^* המקיימת:

  1. לכלx,yΣx,y \in \Sigma^* מתקיים f(x,y){x,y}f(x, y) \in \{x, y\}.
  2. אם xLx \in L או yLy \in L אז f(x,y)Lf(x, y) \in L.
  3. fPOLYf \in \text{POLY}.

נסמן ב-A\mathcal{A} את מחלקת השפות שניתנות לבחירה.

הוכיחו בקצרה את הטענות הבאות.

1. PAP \subseteq \mathcal{A}

2. אם LAL \in \mathcal{A} אז LA\overline{L} \in \mathcal{A}.

3. אם קיימת LAL \in \mathcal{A} שהיא NPC\text{NPC} אז NPANP \subseteq \mathcal{A}.

4. אם קיימת LAL \in \mathcal{A} שהיא NPC\text{NPC} אז P=NP\text{P} = \text{NP}.

1

Answers

1. עבור שפה LL נגדיר

f(x,y)={xif  xLyotherwise f(x, y) = \begin{cases} x & \text{if} \; x \in L \\ y & \text{otherwise} \end{cases}

קל לראות שאם LPL \in \text{P} אז ff היא פונקציית בחירה.

2. עבור שפה LAL \in \mathcal{A} עם פונקציית בחירה ff, נגדיר

f(x,y)={xif  f(x,y)=yyotherwise \overline{f}(x, y) = \begin{cases} x & \text{if} \; f(x, y) = y \\ y & otherwise \end{cases}

קל לראות ש-f\overline{f} היא פונקציית בחירה עבור L\overline{L}.

3. עבור פונקציית בחירה ff של LL,שפה LNPL' \in \text{NP} ורדוקציה ggמ-LL' ל-LL, נגדיר h(x,y)=f(g(x),g(y))h(x, y) = f(g(x), g(y)). קל לראות ש-hh היא פונקציית בחירה עבור LL'.

4. עבור מ"ט א"ד פולינומית, MM, נגדיר את השפה

}\}yy הוא רישא של מסלול מקבל ב-MM על xxLM={(x,y):L_M = \{(x, y) :

קל לראות ש-LMNPL_M \in \text{NP} (למשל על ידי ניחוש המשך המסלול ובדיקה), ולכן, לפי סעיף 3. קיימת לה פונקציית בחירה.

כעת, עבור שפה ב-NP\text{NP}, LL, ומ"ט א"ד פולינומית שמקבלת אותה, MM, נראה איך להכריע בזמן פולינומי אם xLx \in L:

נגדיר

g(x,y)={yy is an acceptance path  yp(x)g(x,f((x,y0),(x,y1))otherwise g(x, y) = \begin{cases} y & \text{y is an acceptance path} \; \lor |y| \geq p(|x|) \\ g(x, f((x, y0), (x, y1)) & \text{otherwise} \end{cases}

כלומר g(x,ε)g(x, \varepsilon) זה מסלול חישוב ב-MM והוא מסלול מקבל אמ"מ xLx \in L.

מכיוון ש-ff פולינומית אז gg גם פולינומית ולכן LPL \in P.

2
Feedback