Question

classification_p_np
subset_sum
partition

בשאלה זו, כל האיברים ei,t,mN+e_i, t, m \in \mathbb{N}_+. בהנחה ש-PNPP \neq NP קבעו עבור כל אחת מהשפות הבאות אם היא ב-PP והוכיחו.

1. L1={(e1,,en,t,m):I[n],I=m,iIei=t}L_1 = \{(e_1, \ldots, e_n, t, m) : \exists I \subseteq [n], |I| = m, \sum_{i \in I} e_i = t\}

2. L2={(e1,,en,t):I[n],iIeit10} L_2 = \{(e_1, \ldots, e_n, t) : \exists I \subseteq [n], |\sum_{i\in I} e_i - t| \leq 10\}

3. L3={(e1,,en,t):I[n],iIeit17,iIei=t} L_3 = \{(e_1, \ldots, e_n, t) : \exists I \subseteq [n], \forall i\in I\; e_i \geq \frac{t}{17}, \sum_{i \in I} e_i = t\}

4. בהנחה ש-P=NPP = NP, הוכיחו כי קיים אלגוריתם יעיל שעל קלט (e1,,en,t)(e_1, \ldots, e_n, t) מוצא I[n]I \subseteq [n] כך ש- iIei=t\sum_{i \in I} e_i = t אם קיימת כזו, או מחזיר קבוצה ריקה אחרת.

1

Answers

1. נשים לב שאם L1PL_1 \in P אז ניתן להכריע את השפה SUBSET-SUM באופן יעיל כך:

  • עבור קלט (e1,,en,s)(e_1, \ldots, e_n, s)
  • עבור 1mn1 \leq m \leq n בדוק אם (e1,,en,s,m)L1(e_1, \ldots, e_n, s, m) \in L_1 ואם כן קבל
  • דחה

המסקנה היא ש-L1PL_1 \notin P.

2. נראה ש-L2PL_2 \notin P על ידי רדוקציה מ-SUBSET-SUM:

f(e1,,en,s)=(100e1,,100en,100s)f(e_1, \ldots, e_n, s) = (100 \cdot e_1, \ldots, 100 \cdot e_n, 100 \cdot s)

נשים לב שהסכום של כל תת קבוצה של e1,,ene_1, \ldots, e_n הוא כפולה של 100 ולכן או שהוא בדיוק שווה ל-100s100 \cdot sהוא שהוא גדול/קטן ממנו בלפחות 100, כלומר (e1,,en,s)SUBSET-SUM(100e1,,100en,100s)L2(e_1, \ldots, e_n, s) \in \text{SUBSET-SUM} \iff (100 \cdot e_1, \ldots, 100 \cdot e_n, 100 \cdot s) \in L_2

3. נשים לב שהאילוצים גוררים ש-I17|I| \leq 17. נראה אלגוריתם יעיל שמכריע את השפה:

  • עבור על כל התת קבוצות של e1,,ene_1, \ldots, e_n בגודל 17 ובדוק אם אחת מהן עונה לדרישות.

לכן L3PL_3 \in P

4. נגדיר את השפה הבאה

L={(e1,,en,t,I[n]):I[n],ΣiIIei=t}L = \{(e_1, \ldots, e_n, t, I \subseteq [n]) : \exists I' \subseteq [n], \Sigma_{i \in I \cup I'}e_i = t\}

קל לראות ש-LNPL \in \text{NP} (מנחשים II' ובודקים).

כעת נתאר את האלגוריתם:

  • אתחל II \leftarrow \emptyset
  • עבור 1in1 \leq i \leq n
  • בדוק אם (e1,,en,t,I{i})L(e_1, \ldots, e_n, t, I \cup \{i\}) \in L ואם כן עדכן II{i}I \leftarrow I \cup \{i\}

מכיוון ש-P=NP\text{P} = \text{NP} אז קיים מימוש יעיל לאלגוריתם הנ"ל. כמו כן קל לוודא את נכונותו.

1
Feedback