Question

p_np

כזכור, הגדרנו את NP כאוסף כל השפות LL כך שקיים יחס SS שהוא:

  • חסום פולינומית
  • ניתן לזיהוי פולינומי
  • L={xy:(x,y)S}L = \{x \mid \exists y : (x,y) \in S\}

בשאלה זו נבחן דרישות אלו ודרישות נוספות שניתן (או לא ניתן) להחיל על SS.

לצורך פשטות, נאמר שהיחס SS מגדיר את השפה LL אם L={xy:(x,y)S}L = \{x \mid \exists y : (x,y) \in S\}.

1. הראו כי אם דורשים כי SS יהיה חסום פולינומית אך לא דורשים שיהיה ניתן לזיהוי פולינומי, ניתן להגדיר גם שפות שאינן ב-NP באמצעות SS.

2. הראו כי אם דורשים כי SS יהיה ניתן לזיהוי פולינומי אך לא דורשים שיהיה חסום פולינומית, ניתן להגדיר גם שפות שאינן ב-NP באמצעות SS.

3. יחס SS יקרא חד-חד ערכי אם ((x1,y)S(x2,y)S)(x1=x2)((x_1,y) \in S \land (x_2,y) \in S) \Rightarrow (x_1 = x_2).

הוכיחו/הפריכו: לכל LNPL \in NP קיים יחס חסום פולינומית, ניתן לזיהוי פולינומי וחד-חד ערכי המגדיר את LL.

4. יחס SS יקרא מונוטוני ממש אם לכל x1,x2,yx_1, x_2, y מתקיים ((x1,y)Sx1x2)((x2,y)S)((x_1,y) \in S \land |x_1| \leq |x_2|) \Rightarrow ((x_2, y) \in S).

הוכיחו/הפריכו: לכל LNPL \in NP קיים יחס חסום פולינומית, ניתן לזיהוי פולינומי ומונוטוני ממש המגדיר את LL.

5. יחס SS יקרא מונוטוני אם לכל x1,x2,y1,y2x_1, x_2, y_1, y_2 מתקיים ((x1,y1)S(x2,y2)Sx1x2)(y1y2)((x_1,y_1) \in S \land (x_2,y_2) \in S \land |x_1| \leq |x_2|) \Rightarrow (|y_1| \leq |y_2|).

הוכיחו/הפריכו: לכל LNPL \in NP קיים יחס חסום פולינומית, ניתן לזיהוי פולינומי ומונוטוני המגדיר את LL.

1

Answers

1. נסתכל על היחס הבא:

}\}המ"ט MM עוצרת על xx : S={((M,x),ε)S = \{((\langle M \rangle, x), \varepsilon)

אז מתקיים ש-

  • היחס חסום פולינומית
  • השפה שהיחס מגדיר היא HP/NP\text{HP} \notin \text{NP}

2. נסתכל על היחס הבא:

}\}המ"ט MM עוצרת על xx תוך tt צעדים: S={((M,x),1t)S = \{((\langle M \rangle, x), 1^t)

אז מתקיים ש-

  • היחס ניתן לזיהוי פולינומי
  • השפה שהיחס מגדיר היא HP/NP\text{HP} \notin \text{NP}

3. הטענה נכונה. עבור שפה LNPL \in \text{NP} ויחס SS שמגדיר אותה נבנה את היחס הבא:

S={(x,x$y):(x,y)S}S' = \{(x, x\$y) : (x, y) \in S\} כאשר $\$ הוא תו שאינו בשימוש ביחס SS. קל לראות שזהו יחס חח"ע, חסום פולינומית וניתן לזיהוי פולינומי.

4. הטענה שגויה. נשים לב שמהטענה נובע שאם מילה באורך ll שייכת לשפה אז גם כל המילים באורך ll ומעלה שייכים לשפה. עבור השפה {1}NP\{1\} \in \text{NP}, למשל, הטענה לא מתקיימת.

5. הטענה נכונה. עבור שפה LNPL \in \text{NP}, יחס מתאים שמגדיר אותה, RR ופולינום מונוטוני לא יורד, PP, שחוסם את היחס, נגדיר את היחס הבא:

{(x,1P(x)y$y):(x,y)R} \{(x, 1^{P(|x|) - |y|}\$y) : (x, y) \in R\}

קל לוודא שזהו אכן יחס מונוטוני שמגדיר את השפה.

1
Feedback