236343 - תורת החישוביות


classification_p_np
sat
proof

בשאלה זו φ\varphi הוא פסוק CNF, ו-nn מספר המשתנים ב φ\varphi. כמו כן נניח ש-P̸=NPP \neq NP.

א. קבעו האם השפות הבאות הן ב-PP והאם הן ב-NPCNPC.

הערה: השמה נותנת ערכים אך ורק למשתני הפסוק.

  1. }\}קיימות (לפחות) 22 השמות שונות המספקות את φ\varphiSAT2={φ:\text{SAT}_2 = \{\varphi :
  2. }\}קיימות 2n2^n השמות שונות המספקות את φ\varphiSAT2n={φ:\text{SAT}_{2^n} = \{\varphi :

ב. הוכיחו/הפריכו: קיימת מ"ט פולינומית אשר בהינתן פסוק φ\varphi והשמה מספקת τ\tau פולטת השמה מספקת τ̸=τ\tau' \neq \tau אם יש כזאת.

classification_p_np
brute_force_search

נאמר על השמה לפסוק CNF שהיא מאוזנת אם מספר המשתנים שמקבלים בה ערך TT שווה למספר המשתנים המקבלים בה ערך FF

בהנחה ש-P̸=NPP \neq NP לכל אחת מהשפות הבאות קבעו האם היא ב-PP או שהיא NPNP-שלמה:

}\}קיימת השמה מספקת מאוזנת ל-φ\varphi L1={φ:L_1 = \{\varphi :

}\}קיימת השמה מספקת,τ\tau, ל-φ\varphi ואינדקס ii כך ש-τ(xj)=T\tau(x_j) = T לכל משתנה פרט אולי ל-xi+1,,xi+lognx_{i + 1}, \dots, x_{i + \log n}L2={φ:L_2 = \{\varphi :

הערה: nn הוא מספר המשתנים של φ\varphi, ו"פרט אולי ל" פירושו שמשתנים אלו יכולים לקבל הן TT והן FF.

r_re
ld
hp

תזכורת: LD={MML(M)}\overline{L_D} = \{\langle M \rangle | \langle M \rangle \notin L(M)\}.

  1. הציגו הוכחה ישירה (מבלי להשתמש בשפות אחרות) ש-LDRE\overline{L_D} \notin RE.
  2. הוכיחו: HPLD\overline{HP} \leq \overline{L_D}.
classification_p_np
vertex_cover
independent_set

בהנחה ש P̸=NPP \neq NP קבעו עבור כל שפה האם היא ב-PP. הוכיחו את תשובתכם.

1. }\}קיים ל-GG כיסוי בצמתים בגודל kk או קבוצה בלתי תלויה בגודל kk L1={(G,k):L_1 = \{(G,k) :

2. }\}קיים ל-GG כיסוי בצמתים בגודל kk וגם קבוצה בלתי תלויה בגודל kk L2={(G,k):L_2 = \{(G,k) :

3. }\}GG קשיר וקיים ל-GG כיסוי בצמתים בגודל kk שהוא גם קבוצה בלתי תלויה L3={(G,k):L_3 = \{(G,k) :

classification_r_re

עבור מ"ט M1M_1 ו-M2M_2 נסמן fM1(x)=fM2(x)f_{M_1}(x) = f_{M_2}(x) אם שתי המכונות עוצרות בריצה על xx והפלט שלהן זהה. עבור כל אחת מהשפות הבאות קבעו האם היא ב- R, והאם היא ב-RE.

  • }\}לכל MM' ו-xx, fM(M,x)=1f_M(\langle M' \rangle, x) = 1 אם MM' עוצרת על xx ו-0 אחרת L1={M:L_1 = \{\langle M \rangle :
  • L2={(M1,M2):x,fM1(x)=fM2(x)}L_2 = \{(\langle M_1 \rangle, \langle M_2 \rangle) : \forall x, \: f_{M_1}(x) = f_{M_2}(x)\}
  • L3={(M1,M2):x,fM1(x)=fM2(x)}L_3 = \{(\langle M_1 \rangle, \langle M_2 \rangle) : \exists x, \: f_{M_1}(x) = f_{M_2}(x)\}
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 :

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.

model

מודל מ"ט בגיל העמידה לחישוב פונקציות הוא מודל זהה למודל הסטנדרטי של מ"ט לחישוב פונקציות פרט לשינויים הבאים:

  • למכונה אין מצבים סופיים, ולכן המכונה לעולם לא עוצרת.
  • נגיד שמכונה נעמדת בצעד החישוב ה tt אם מצעד חישוב זה והלאה המכונה מבצעת אך ורק תזוזות Stay ולעולם לא תבצע יותר תזוזות Left או Right
  • עבור קלט xx פלט המכונה הוא המילה yy שנמצאת משמאל לראש כאשר המכונה נעמדת.

קבעו האם מודל זה שקול למודל הסטנדרטי. אם כן נמקו באמצעות תיאור מילולי משכנע של סימולציה מתאימה. אם לא הוכיחו במדיוק.

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 אם קיימת כזו, או מחזיר קבוצה ריקה אחרת.

k-clique
p
bipartite_graph

בהנחה ש-PNPP \neq NP הוכיחו/הפריכו:

השפה

}\}הגרף GG הוא גרף דו צדדי וקיים בו קליק בגודל kk L={G,k:L = \{G, k :

ב-PP.

classification_p_np
sat

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

1. }\}מתקיים φSAT\varphi \in SAT ויש בו לפחות 100 פסוקיות L1={φ:L_1 = \{\varphi :

2. }\}מתקיים φSAT\varphi \in SAT ויש בה לכל היותר 100 פסוקיותL2={φ:L_2 = \{\varphi :

3. }\}מתקיים φSAT\varphi \in SAT מכיל nn משתנים ולפחות 2n2^n פסוקיותL3={φ:L_3 = \{\varphi :

spring_18_a
r_re

עבור מכונת טיורינג, MM, נסמן ב-R(M)R(M) את קובצת המילים אותן MM דוחה, כלומר }\}MM דוחה את xx R(M)={xΣ:R(M) = \{x \in \Sigma^* :

1. תארו בקצרה זוג מכונות M,MM, M' כך ש-R(M)̸=R(M)R(M) \neq R(M') אבל L(M)=L(M)L(M) = L(M').

לכל אחת מהשפות הבאות קבעו אם היא ב-R\text{R} והאם היא ב-RE\text{RE}:

2. }\}קיימת M̸=MM' \neq M כך ש-R(M)=R(M)R(M) = R(M') L1={M:L_1 = \{\langle M \rangle :

3. L2={M:R(M)2}L_2 = \{\langle M \rangle : |R(M)| \geq 2\}

4. }\}קיימת M̸=MM' \neq M כך ש-R(M)=R(M)R(M) = R(M') ובנוסף L3={M:L(M)̸=L(M)L_3 = \{ \langle M \rangle : L(M) \neq L(M')

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}.

classification_p_np
dominating_set
vertex_cover

עבור גרף לא מכוון G=(V,E)G = (V, E) נגדיר קבוצה שולטת כתת קבוצה של צמתים DVD \subseteq V כך שלכל צומת vVDv \in V \setminus D יש שכן ב- DD, כלומר קיים uDu \in D כך ש-(u,v)E(u, v) \in E. נזכיר כי כיסוי בצמתים של GG הוא קבוצהSVS \subseteq V כך שלכל קשת {u,v}E\{u,v\} \in E מתקיים {u,v}S\{u,v\} \cap S \neq \emptyset.

הערה: בשאלה זו ניתן להניח ש-GG קשיר.

  1. הוכיחו / הפריכו: אם SVS \subseteq V היא כיסוי בצמתים של GG אז היא קבוצה שולטת ב-GG.
  2. הוכיחו / הפריכו: אם DVD \subseteq V היא קבוצה שולטת ב-GG אז היא כיסוי בצמתים של GG.

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

  • }\}יש ב-GG קבוצה שולטת בגודל V10|V| - 10L1={G:L_1 = \{G :
  • }\}יש ב GG קבוצה שולטת בגודל kk DS={(G,k):DS = \{(G, k) :
  • }\}יש ב GG קבוצה שולטת בגודל kk DSk={G:DS_k = \{G :
classification_r_re

עבור כל אחת מהשפות הבאות קבעו האם היא שייכת ל-RR והאם היא שייכת ל-RERE:

}\}קיימת מ"ט MM' כך ש-MM' מקבלת את xx או ש-MM מקבלת את M\langle M' \rangle : L1={(M,x)L_1 = \{(\langle M \rangle, x)

}\}קיימת מ"ט MM' כך ש-MM' מקבלת את xx וגם MM מקבלת את M\langle M' \rangle : L2={(M,x)L_2 = \{(\langle M \rangle, x)

}\}לכל מ"ט MM' ,MM' מקבלת את xx או ש-MM מקבלת את M\langle M' \rangle : L3={(M,x)L_3 = \{(\langle M \rangle, x)

}\}לכל מ"ט MM' ,MM' מקבלת את xx וגם MM מקבלת את M\langle M' \rangle : L4={(M,x)L_4 = \{(\langle M \rangle, x)

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-עצמית מקצרת.
reduction_p_np
3col

פסוק 2CNF2CNF_{\neq} זהה לפסוק 2CNF2CNF פרט לאופן שבו מוגדרים ליטרלים והשמה:

  • כל ליטרל בפסוק הוא מהצורה xibx_i \neq b כאשר b{1,2,3}b \in \{1, 2, 3\}
  • השמה היא פונקציה f:V{1,2,3}f:V \to \{1, 2, 3\} כלומר נותנת לכל משתנה ערך בן 1 ל 3.
  • ערך של ליטרל xibx_i \neq b הוא TT אם f(xi)bf(x_i) \neq b

דוגמה:

הפסוק הבא ספיק עבור ההשמה f(x1)=f(x2)=2f(x_1) = f(x_2) = 2:

(x11x22)(x12x21) (x_1 \neq 1 \lor x_2 \neq 2) \land (x_1 \neq 2 \lor x2 \neq 1)
  • הוכיחו: השפה הבאה היא NPCNPC

}\}הפסוק φ\varphi הוא פסוק 2CNF2CNF_{\neq} ספיקL1={φ:L_1 = \{\varphi :

הדרכה: קיימת רדוקציה מ-3COL3COL.

spring_18_a
p_np

תזכורת: גרף לא מכוון, G=(V,E)G = (V,E) הוא גרף דו צדדי עם ניתן לחלק את VV לשתי קבוצות זרות C,DC, D כך שלכל קשת ב-EE מתקיים שצד אחד שלה ב-CC והשני ב-DD.

הערה: בסעיפים הבאים ניתן להניח כי כל הגרפים קשירים.

בהנחה ש-P̸=NP\text{P} \neq \text{NP}, קבעו לכל אחת מהשפות הבאות האם היא ב-P\text{P} או שהיא NP\text{NP}-שלמה.

1. }\}GG הוא גרף דו צדדי לא מכוון וקיים ב-GG מעגל המילטוני L1={G:L_1 = \{G :

רמז: בהינתן גרף GG, צרו גרף GG' אשר קבוצת צמתיו מתקבלת מהחלפת כל צומת vVv \in V בארבעה צמתים v1,v2,v3,v4v_1, v_2, v_3, v_4, כך ש-GG' דו צדדי ומתקיים ש-v1,v3Cv_1, v_3 \in C ו-v2,v4Dv_2, v_4 \in D.

בהינתן גרף דו צדדי לא מכוון, G=(CD,E)G = (C \cup D, E), נאמר ש-GG הוא גרף מרכזים אם לכל צומת vDv \in D דרגתו היא בדיוק 2.

2. }\}GG הוא גרף מרכזים וקיים ב-GG מעגל המילטוני L2={G:L_2 = \{G :

3. }\}GG הוא גרף מרכזים וקיים ב-GG מעגל העובר בכל צומת ב-CC בדיוק פעם אחת L3={G:L_3 = \{G :

p_np
proof

בהינתן שפה LL, נסמן ב LL^* את סגור קליני של השפה: כל המילים שהן שרשורים של מספר סופי של מילים מ-LL:

L={w1wk:w1,,wkL,kN} L^* = \{w_1 \cdots w_k : w_1,\ldots,w_k \in L, k \in \mathbb{N}\}

א. הוכיחו כי אם LNPL \in NP אז גם LNPL^* \in NP. הוכיחו את תשובתכם פעם אחת על ידי תיאור יחס מתאים ופעם נוספת על ידי תיאור מ"ט א"ד פולינומית מתאימה.

ב. הוכיחו כי אם LPL \in P אז גם LPL^* \in P.

rice

נאמר ששפה LL היא טריוויאלית אם L=L = \emptyset או L=ΣL = \Sigma^* ונאמר שתכונה SRES \subseteq RE היא טריוויאלית אם S=S = \emptyset או S=RES = RE

הוכיחו/הפריכו את הטענות הבאות:

א. לכל זוג שפות לא טריוויאליות L1,L2RL_1,L_2 \in R מתקיים L1L2L_1 \leq L_2.

ב. לכל זוג תכונות לא טריוויאליות S1,S2RES_1,S_2 \subset RE מתקיים LS1LS2L_{S_1} \leq L_{S_2} (כזכור, LS={M:L(M)S}L_S = \{\langle M \rangle : L(M) \in S\})

ג. לכל זוג שפות L1,L2/REL_1,L_2 \notin RE מתקיים L1L2L_1 \leq L_2

r_re

עבור שפות L1,L2L_1, L_2 נגדיר את ההפרש הסימטרי שלהן L1L2L_1 \triangle L_2 כאוסף המילים xx כך ש-xL1L2x \in L_1 \setminus L_2 או xL2L1x \in L_2 \setminus L_1 (כלומר אוסף המילים השייכות בדיוק לאחת מבין שתי השפות L1,L2L_1, L_2).

עבור אוסף מכונות C={M1,M2,}C = \{\langle M_1 \rangle, \langle M_2 \rangle, \dots\} המכיל לפחות שני קידודים של מכונות, נאמר ש-DD מבחין של CC אם DD מ"ט המקבלת כקלט זוג קידודי מכונות (M1,M2)(\langle M_1 \rangle, \langle M_2 \rangle), ואם M1,M2CM_1, M_2 \in C אז DD פולטת xL(M1)L(M2)x \in L(M_1) \triangle L(M_2) אם קיים כזה, ואחרת DD לא עוצרת.

אם (M1,M2)(\langle M_1 \rangle, \langle M_2 \rangle) לא שתיהן ב-CC, המבחין DD יכול להתנהג איך שהוא רוצה.

הערה: שימו לב ש-DD לא יכול לקבוע איזה מכונות נמצאות באוסף ואיזה לא, אבל זה לא משנה מכיוון שאם אחת מהן לא ב-CC, כל התנהגות של DD מתקבלת.

בכל אחד מהסעיפים הבאים קבעו האם קיים מבחין DD לכל אוסף מכונות CC המקיים את התנאים בסעיף:

1. CC אוסף קידודי מכונות כלשהו.

2. CC אוסף קידודי מכונות כך שלכל MC\langle M \rangle \in C מתקיים L(M)RL(M) \in \text{R}.

3. CC המקיים שלכל MC\langle M \rangle \in C, MM מכריעה את השפה L(M)L(M).

r_re
proof

הוכיחו/הפריכו את הטענות הבאות:

א. אם L1RERL_1 \in RE \setminus R וגם L2coRERL_2 \in coRE \setminus R אז L1L2/RL_1 \cup L_2 \notin R

ב. אם L1REL_1 \in RE וגם L2coREL_2 \in coRE אז L1L2RL_1 \cap L_2 \in R

ג. אם L1RERL_1 \in RE \setminus R וגם L2RERL_2 \in RE \setminus R אז L1L2/RL_1 \cup L_2 \notin R

הערה: בסעיף זה, במידה ומציגים שפה LRERL \in RE \setminus R, אין צורך להוכיח את הסיווג של LL, מספיק לנמק בקצרה.

ד. אם L1/RL_1 \notin R ו- L2L_2 שפה סופית אז L1L2/RL_1 \cup L_2 \notin R

classification_r_re

עבור מ"ט דטרמיניסטית MM, נסמן ב M\overline{M} את המ"ט המתקבלת על ידי היפוך המצבים הסופים. כלומר המצב המקבל ב-MM הוא המצב הדוחה ב-M\overline{M} וההיפך.

עבור כל אחת מהשפות הבאות קבעו האם היא ב-RR, האם היא ב-RERE והאם היא ב-coREcoRE.

L1={M:w,wL(M)L(M)}L_1 = \{\langle M \rangle :\exists w,w \in L(M) \cap L(\overline{M})\}

L2={M:w,wL(M)L(M)}L_2 = \{\langle M \rangle :\exists w,w \in L(M) \cup L(\overline{M})\}

L3={M:w,wL(M)L(M)}L_3 = \{\langle M \rangle :\exists w,w \notin L(M) \cup L(\overline{M})\}

L4={M:w,wL(M)L(M)}L_4 = \{\langle M \rangle :\forall w,w \in L(M) \cup L(\overline{M})\}

הגדרה: עבור מחלקת שפות C , שפה L1 היא שלמה בC , אם היא שייכת לC , וכן לכל L2 L2 ∈ C ניתנת לרדוקציה ל L2 ≤ L1) L1)

הוכח או הפרך:

  • קיימת שפה שלמה בRE ∪ coRE.
  • קיימת שפה שלמה בcoRE.
  • קיימת שפה שלמה לקבוצת כל השפות P(Σ∗).
proof
p_np
r_re

שפה LL תקרא שלמה ביחס למחלקת שפות SS אם:

  • מתקיים ש-LSL \in S
  • לכל LS{Σ,}L' \in S \setminus \{\Sigma^*, \emptyset\} מתקיים LpLL' \leq_{p} L.

לכל אחת ממחלקות השפות הבאות, קבעו האם יש שפה שלמה ביחס אליה. הוכיחו את תשובתכם.

  • NP
  • P
  • RE \cup coRE
  • קבוצת כל השפות מעל האלפבית {0,1}\{0,1\}
p_np
independent_set
set_cover

בשאלה זו נניח כי P̸=NP\text{P} \neq \text{NP}. עבור כל שפה מהשפות הבאות, קבע האם היא ב-P\text{P} או לא.

הערה: בכל הסעיפים הבאים, CiC_i, מסמן קבוצה, ו-kk מסמן מספר טבעי.

1. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שחיתוכן ריק L1={(C1,,Cm,k):L_1 = \{(C_1, \dots, C_m, k) :

2. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שכל זוג ביניהן זרותL2={(C1,,Cm,k):L_2 = \{(C_1, \dots, C_m, k) :

3. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שאיחודן מכיל קבוצה אחרת L3={(C1,,Cm,k):L_3 = \{(C_1, \dots, C_m, k) :

4. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שאיחודן מוכל בקבוצה אחרתL4={(C1,,Cm,k):L_4 = \{(C_1, \dots, C_m, k) :

r_re

תזכורת: Lk={M:L(M)k}L_{\geq k} = \{\langle M \rangle : |L(M)| \geq k\}

הוכיחו או הפריכו את הטענות הבאות:

  1. קיימת מ"ט MM כך ש-L(M)=1020|L(M)| = 10^{20}.
  2. קיימת מ"ט MM כך ש-L4L(M)L3L_{\geq 4} \subset L(M) \subset L_{\geq 3}.
  3. קיימת מ"ט MM כך ש-L3L(M)L4L_{\leq 3} \subset L(M) \subset L_{\leq 4}.
misc

הוכיחו/הפריכו: קבוצת המספרים הרציונליים היא בת מניה.

classification_p_np
approximation

בשאלה זו nn ו-kk מספרים שלמים, ו-Si[n]S_i \subseteq [n]. כמו כן נניח כי PNPP \neq NP. קבעו לכל שפה האם היא ב-PP והאם היא ב-NPCNPC.

1. }\}קיימות kk קבוצות זרות מבין הקבוצות S1,,SmS_1, \ldots, S_m L1={(n,k,S1,,Sm):L_1 = \{(n, k, S_1, \ldots, S_m ):

2. }\}S1,,SmS_1, \ldots, S_m ניתנות לחלוקה L2={(n,S1,,Sm):L_2 = \{(n, S_1, \ldots, S_m ):

כאשר S1,,SmS_1, \ldots, S_m ניתנות לחלוקה אם ניתן לחלק את הקבוצות לשתי מחלקות זרות כך שהקבוצות בכל מחלקה זרות זו לזו. פורמאלית, S1,,SmS_1, \ldots, S_m ניתנות לחלוקה אם קיימות שתי קבוצות זרות A,B[m]A,B \subseteq [m] שמקיימות AB=[m]A \cup B = [m] וכן לכל ijAi \neq j \in A מתקיים SiSj=S_i \cap S_j = \emptyset ולכל ijBi \neq j \in B מתקיים SiSj=S_i \cap S_j = \emptyset.

3. }\}קיימות kk קבוצות כמעט זרות ב-S1,,SmS_1, \ldots, S_m L3={(n,k,S1,,Sm):L_3 = \{(n, k, S_1, \ldots, S_m ):

כאשר קבוצות נקראות כמעט זרות אם בחיתוך של כל שתי קבוצות קיים איבר אחד לכל היותר.

נסמן ב-f(S1,,Sm)f(S_1, \ldots, S_m ) את המספר המקסימלי של קבוצות זרות ב-S1,,SmS_1, \ldots, S_m .

4. הוכיחו: לא קיימת מ"ט פולינומית שמחשבת את ff.

5. הוכיחו/הפריכו: קיים אלגוריתם יעיל המקרב את ff עד כדי קבוע חיבורי 3.

model
basic

עבור כל אחד מרצף הקונפיגורציות הבאות כתבו מה ניתן להסיק על פונקצית המעברים δ\delta, או הסבירו מדוע לא יתכן רצף כזה.

הערה: האינדקס של התא הראשון בסרט הוא 0. בתיאור הקונפיגורציות הסרט מתואר משמאל לימין.

  1. [q7,3,0000][q3,2,0001][q2,2,0011][q_7, 3, 0000] \to [q_3, 2, 0001] \to [q_2, 2, 0011]
  2. [q1,3,0000][q5,1,0001][q6,2,0001][q_1, 3, 0000] \to [q_5, 1, 0001] \to [q_6, 2, 0001]
  3. [q2,1,0000][q1,2,0001][q3,3,0001][q_2, 1, 0000] \to [q_1, 2, 0001] \to [q_3, 3, 0001]
  4. [q2,1,0000][q2,1,0000][q3,1,0000][q_2, 1, 0000] \to [q_2, 1, 0000] \to [q_3, 1, 0000]
sat
misc
eli

נגדיר מחלקת שפות חדשה CC. שפה LL שייכת למחלקה CC אם קיימת מ"ט פולינומית הסתברותית, MM, שמקיימת את התנאים הבאים:

  • לכל wLw \in L, MM מקבלת את ww בהסתברות גדולה או שווה ל-2n2^{-n} (כאשר nn אורך הקלט)
  • לכל w/Lw \notin L, MM דוחה את ww.

הוכיחו: SATC\text{SAT} \in C.

misc
p_np

תזכורת: שפה LCL \in C תקרא שלמה ביחס למחלקה CC אם לכל שפה LCL' \in C מתקיים LpLL' \leq_p L (קיימת רדוקציה פולינומית מ-LL' ל-LL).

ענו על הסעיפים הבאים בהנחה ש-NP̸=coNPNP \neq coNP.

1. הוכיחו: LNPL \in NP שפה שלמה ביחס ל-NPNP, אם ורק אם L\overline{L} שפה שלמה ביחס ל-coNPcoNP.

2. בהנחה ש-NP̸=coNP\text{NP} \neq \text{coNP} הוכיחו/הפריכו: קיימת שפה LNPL \in NP כך ש-LL שלמה ביחס ל-NPNP וגם L\overline{L} שלמה ביחס ל-NPNP.

reduction_p_np

רוצים להושיב nn אנשים בשורה. כל בן אדם רשאי לתת רשימה של אנשים, לידם הוא לא מעוניין לשבת. צריך להכריע האם קיים סדר ישיבה כזה כך שאף בן אדם לא יושב ליד מישהו שהוא לא מעוניין.

  1. הראו שלא ניתן לפתור את הבעיה בצורה יעילה בהנחה ש-P̸=NP\text{P} \neq \text{NP}.
  2. הראו שקיים פתרון יעיל לבעיה אם P=NP\text{P} = \text{NP}.
rice

נאמר ששפה LL היא לא טריוויאלית אם Lϕ,ΣL \neq \phi, \Sigma^*.

הוכיחו או הפריכו כל אחת מהטענות הבאות:

  1. לכל זוג שפות לא טריוויאליות L1L_1, L2L_2 כך ש-L1,L2RL_1, L_2 \in R מתקיים L1L2L_1 \leq L_2.
  2. לכל זוג שפות לא טריוויאליות L1L_1, L2L_2 כך ש-L1,L2REL_1, L_2 \in RE מתקיים L1L2L_1 \leq L_2.
r_re
diagonal_lemma

בהקשר של מכונות טיורינג, לכסון הוא בניה של מכונה UU ששפתה בהכרח לא מתקבלת על ידי מכונה מתוך מחלקה מסוימת של מכונות, על ידי כך שמבטיחים ש-UU תתנהג שונה מכל מכונה במחלקה זו על קלט מסויים.

1. נציע את הבניה הבאה: UU על קלט ww מפרשת את ww כמכונת טיורינג לזיהוי שפות w=Mw = \langle M \rangle, מריצה את MM על ww, ואם MM עצרה, UU עונה הפוך ממנה. הוכיחו כי L(U)RL(U) \notin R (בכך סיפקנו הוכחה נוספת לקיום שפות שאינן ב-RR).

2. בבירור L(U)REL(U) \in RE על פי הגדרת RERE כמחלקת השפות שיש מכונת טיורינג שמקבלת אותן. סטודנט מתחכם טען כי התגלתה סתירה במתמטיקה שכן סעיף 1 מוכיח "באותה צורה בדיוק" ש-L(U)REL(U) \notin RE. היכן הטעות?

3. הוכיחו בלכסון: קיימת שפה ב-RR כך שלא קיימת מ"ט המקבלת אותה ומבצעת לכל היותר O(n)O(n) צעדים על קלט באורך nn.

הדרכה: בנו מכונה UU המפרשת את הקלט שלה כ-w=1k0Mw = 1^k0\langle M \rangle.

reduction_p_np
set_cover

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

1. מנהל הטכנולוגיות הראשי של הסטארטאפ מבקש ממכם למצוא אלגוריתם יעיל לבעיה כתלות במספר הסופרמרקטים ומספר המוצרים השונים איתם עובד האתר. שכנעו את מנהל הטכנולוגיות הראשי שלא כדאי להשקיע בכך זמן.

2. בזכות התחרות האגרסיבית בין הסופרמרקטים השונים, כל הסופרמרקטים מציעים ללקוחות משלוחים חינם. האם עכשיו ניתן לפתור את הבעיה באופן יעיל ?

3. הסטארטאפ החליט שהוא עובד עם 10 סופרמרקטים בלבד. הציעו אלגוריתם לבעיה.

classification_p_np
3col

נאמר שגרף ניתן לכיסוי על ידי kk קליקים אם קיימת חלוקה של צמתי הגרף ל-kk קבוצות כך שכל קבוצה משרה קליק (גרף מלא).

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

  • }\}הגרף GG ניתן לכיסוי על ידי 3 קליקים L1={G:L_1 = \{G :
  • }\}הגרף GG ניתן לכיסוי על ידי 2 קליקים L2={G:L_2 = \{G :
  • }\}הגרף GG גרף דו צדדי והוא ניתן לכיסוי על ידי kk קליקים L3={(G,k):L_3 = \{(G, k) :
3col
true_false

לכל אחת מהטענות הבאות קבעו האם היא נכונה, שגויה או שקולה לבעיה פתוחה מוכרת. הוכיחו בקצרה.

1. קיים אלגוריתם יעיל שבהנתן גרף GG ומספר kk פולט kk צביעה חוקית של GG או 0 אם אין כזו.

2. קיים אלגוריתם יעיל שבהינתן גרף GG פולט צביעה מינימלית של GG.

תזכורת: צביעה מינימלית של GG הינה צביעה חוקית של צמתי GG המשתמשת במספר המינימלי של צבעים האפשרי בשביל לצבוע את GG.

r_re
proof

תהיינה f1f_1 ו- f2f_2 פונקציות מלאות. נגדיר: Lf1,f2={x:f1(x)>f2(x)}L_{f_1,f_2} = \{x : f_1(x) > f_2(x)\}.

הוכיחו/הפריכו:

1. אם f1f_1 ו-f2f_2 ניתנות לחישוב אז Lf1,f2RL_{f_1,f_2} \in R.

2. אם Lf1,f2RL_{f_1,f_2} \in R אז f1f_1 ו-f2f_2 ניתנות לחישוב.

3. אם f1f_1 מונוטונית יורדת ממש ו- f2f_2 מונוטונית עולה ממש אז Lf1,f2RL_{f_1,f_2} \in R.

true_false_open
winter17-18

עבור כל אחת מהטענות הבאות קבעו האם היא נכונה, לא נכונה או שקולה לפתרון בעיה פתוחה, והוכיחו תשובתכם.

  1. השפה VCPSPACE\overline{VC} \notin \text{PSPACE}.
  2. אם קיימת ל-SAT מ"ט הרצה בזמן nO(logn)n^{O(\log n)} אז לכל LNPL \in NP קיימת מ"ט שרצה בזמן nO(logn)n^{O(\log n)}.
  3. לא קיימת מ"ט פולינומית MM כך ש-fM(G)|f_M(G)| (אורך הפלט של MM על GG) שווה לאורך המעגל הפשוט הארוך ביותר ב-GG.
classification_r_re
vertex_cover
independent_set

תזכורת: ניתן לסמלץ מ"ט דטרמיניסטית בזמן שהוא ריבועי במספר הצעדים שמסמלצים.

עבור מ"ט דטרמיניסטית, MM, נסמן ב-fMf_M את הפונקציה אותה מחשבת המכונה.

עבור כל אחת מהשפות הבאות קבעו האם היא ב-R, האם היא ב-RE והאם היא ב-coRE. הוכיחו את תשובתכם.

1. }\}הפונקציה fMf_M היא רדוקציה מ-HP\text{HP} ל-VC\text{VC} L1={M:L_1 = \{\langle M \rangle :

2. }\}fMf_M היא רדוקציה מ-VC\text{VC} ל-IS\text{IS} שרצה בזמן p(n)p(n) לכל היותר L2={(M,p):L_2 = \{(\langle M \rangle, p) :

הערה: p:NNp: \mathbb{N} \to \mathbb{N} היא פולינום, nn אורך הקלט.

3. }\}הפונקציה fMf_M היא רדוקציה פולינומית מ-VC\text{VC} ל-IS\text{IS} L3={M:L_3 = \{\langle M \rangle :

p_np
vertex_cover

קבוצה בלתי תלויה בגרף היא תת קבוצה של צמתים IVI \subseteq V כך ש-G[I]G[I] חסר קשתות.

קליק בגרף הוא תת קבוצה של צמתים KVK \subseteq V כך ש-G[K]G[K] גרף מלא.

נתונות השפות הבאות:

}\}בגרף GG קיים כיסוי בצמתים בגודל kk VC={(G,k):\text{VC} = \{(G,k) :

}\}בגרף GG קיימת קבוצה בלתי תלויה בגודל kk IS={(G,k):\text{IS} = \{(G,k) :

}\}בגרף GG קיים קליק בגודל kk CLIQUE={(G,k):\text{CLIQUE} = \{(G,k) :

1. הראו ש-VCpIS\text{VC} \leq_p \text{IS}.

2. הראו ש-ISpCLIQUE\text{IS} \leq_p \text{CLIQUE}.

3. הראו ש-CLIQUEpVC\text{CLIQUE} \leq_p \text{VC}.

4. הוכיחו: השפה }\}בגרף GG קיים כיסוי בצמתים בגודל 3VC3={(G):\text{VC}_3 = \{(G) : שייכת ל PP.

p_np
proof
sat

נסמן L1p1L2L_1 \leq_p^1 L_2 אם קיימת רדוקציה פולינומית חח"ע מ-L1L_1 אל L2L_2.

תזכורת: פונקציה ff היא חח"ע אם לכל xyx \neq y מתקיים f(x)f(y)f(x) \neq f(y). ענו בקצרה על הסעיפים הבאים:

  1. הוכיחו: לכל שפה LL מתקיים Lp1LL \leq_p^1 L.
  2. הוכיחו: היחס p1\leq_p^1 טרנזיטיבי, כלומר אם L1p1L2L_1 \leq_p^1 L_2 וגם L2p1L3L_2 \leq_p^1 L_3 אז L1p1L3L_1 \leq_p^1 L_3.
  3. הוכיחו: אם לכל L1,L2NPCL_1,L_2 \in NPC מתקיים L1p1L2L_1 \leq_p^1 L_2 אזי PNPP \neq NP.
  4. הוכיחו: לכל שפה LNPL \in NP מתקיים Lp1SATL \leq_p^1 SAT.
pspace

נגדיר את מחלקת השפות P\oplus P:

שפה LL נמצאת ב-P\oplus P אם קיימת מ"ט א"ד פולינומית MM כך ש:

  • לכלxLx \in L מספר המסלולים המקבלים של MM הוא אי זוגי.
  • לכלxLx \notin L מספר המסלולים המקבלים של MM הוא זוגי.

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

  • הוכיחו/הפריכו: PPSPACE\oplus P \subseteq \text{PSPACE}.
  • הוכיחו/הפריכו: אם L1,L2PL_1,L_2 \in \oplus P אז L1L2PL_1 \cap L_2 \in \oplus P.
winter17-18
classification_r_re

נאמר ש-xx מילה מקסימלית המתקבלת ע"י MM אם xL(M)x \in L(M) ולכל yL(M)y \in L(M) מתקיים yx|y| \leq |x|.

לכל אחת מהשפות הבאות קבעו האם היא ב-R והאם היא ב-RE.

  1. x}x\} מילה מקסימלית המתקבלת ע"י MM L1={M,x:L_1 = \{\langle M \rangle, x :
  2. M}M\} מקבלת את xx ו-xx אינה מילה מקסימלית המתקבלת ע"י MM L2={M,x:L_2 = \{\langle M \rangle, x :
  3. x}x\} מילה מקסימלית המתקבלת ע"י MM תוך x|x| צעדים L3={M,x:L_3 = \{\langle M \rangle, x :
eli
ip

השפה

}\}הגרפיםG1G_1 ו-G2G_2 לא איזומורפיים GNI={(G1,G2):\text{GNI} = \{(G_1, G_2) :

שייכת למחלקה (IP (Interactive Proofs

ופרוטוקול ההוכחה הוא:

  • המוודא בוחר את אחד הגרפים באקראי, G=(V,E)G = (V, E)
  • המוודא בוחר פרמוטציה אקראית, f:[n][n]f:[n] \to [n] ושולח למוכיח את G=(f(V),f(E))G' = (f(V), f(E))
  • המוכיח שולח למוודא איזה גרף נבחר בשלב 1.
  • חוזרים על שלבים 1 - 3 פעמיים והמוודא מקבל אם המוכיח ענה שתי תשובות נכונות.

כזכור, LIPL \in IP אם קיים פרוטוקול פולינומי שמקיים את שתי התכונות הבאות:

  • שלמות: אם xLx \in L אז קיים מוכיח שיגרום למוודא לקבל את xx.
  • נאותות: אם x/Lx \notin L אז לכל מוכיח ההסתברות שהמוודא יקבל את xx קטנה מחצי.

הראו שהפרוטוקול הנ"ל שלם ונאות:

  • שלמות: אם (G1,G2)L(G_1, G_2) \in L אזי:
  • נאותות: אם (G1,G2)/L(G_1, G_2) \notin L אזי:
classification_r_re

עבור כל אחת מהשפות הבאות קבעו האם היא שייכת ל-RR והאם היא שייכת ל-RERE:

1. }\}המ"ט MM מקבלת את xx תוך y|y| צעדים L1={(M,x,y)L_1 = \{(\langle M \rangle, x, y) \mid

2. L2={(M,x)y,y>x:yL(M)}L_2 = \{(\langle M \rangle, x) \mid \exists y, |y| > |x| : y \in L(M)\}

3. L3={(M,x)y,y>x:yL(M)L_3 = \{(\langle M \rangle, x) \mid \forall y, |y| > |x| : y \in L(M)

reduction_p_np
hamiltonian_path

הוכיחו שהשפות הבאות הן NP-שלמות (kk מספר שלם):

1. }\}קיים ב GG מעגל המילטוני שעובר בקשת ee L1={(G,e):L_1 = \{(G,e) :

2. }\}קיים ב GG מעגל פשוט באורך 2k2k L2={(G,k):L_2 = \{(G,k) :

3. }\}הגרף GG הוא גרף דו צדדי מכוון שמכיל מסלול המילטוני L3={G:L_3 = \{G :

r_re
proof

תהיינה S1S_1 ו- S2S_2 תכונות של שפות ב RERE. נגדיר

LS1,S2={(M1,M2):L(M1)S1L(M2)S2} L_{S_1, S_2} = \{(\langle M_1 \rangle, \langle M_2 \rangle) : L(M_1) \in S_1 \land L(M_2) \in S_2\}

עבור כל אחד מהמשפטים הבאים קבעו האם הוא נכון או לא. הוכיחו את תשובתכם.

1. השפה LS1,S2RL_{S_1,S_2} \in R אם"ם S1S_1 ו-S2S_2 טריוויאליות.

2. השפה LS1,S2RL_{S_1,S_2} \in R אם"ם S1S_1 או S2S_2 טריוויאליות.

3. השפה LS1,S2RL_{S_1,S_2} \in R אם"ם S1=S_1 = \emptyset או S2=S_2 = \emptyset או S1=S2=RES_1 = S_2 = RE.

classification_p_np
steiner_tree

בשאלה זו נניח ש-P̸=NPP \neq NP. בסעיפים הבאים GG הוא גרף לא מכוון עם משקלים על הקשתות. קבעו לכל אחת מהשפות הבאות האם היא ב-PP והאם היא ב-NPNP.

1. }\}קיים ל-GG עץ פורס במשקל ww לכל היותר ובעל דרגה מקסימלית dd L1={(G,d,w):L_1 = \{(G, d, w):

2. }\}קיים ל-GG עץ פורס במשקל ww לכל היותר ובעל דרגה ממוצעת dd L2={(G,d,w)):L_2 = \{(G, d, w)):

בסעיפים הבאים, בהינתן גרף לא מכוון וממושקל, G=(V,E)G = (V, E), שורש rVr \in V וקבוצת "טרמינלים" TVT \subseteq V, נגדיר עץ שטיינר כעץ, G=(V,E)G' = (V', E'), שמקיים:

  • {r}TVV\{r\} \cup T \subseteq V' \subseteq V
  • EEE' \subseteq E

כלומר עץ שטיינר הוא תת גרף של GG שמכיל את כל הטרמינלים והשורש והוא עץ. נגיד שעץ שטיינר הוא בעומק 2 אם בנוסף מתקיים   vV,d(v,r)2\forall \; v \in V', d(v, r) \leq 2.

3. הוכיחו: השפה הבאה היא ב- NPC:

}\}קיים ל-GG עץ שטיינר בעומק 2 ובמשקל ww לכל היותר L3={(G=(V,E),TV,r,w)):L_3 = \{(G = (V, E), T \subseteq V, r, w)):

4. הוכיחו: הפונקציה ff שמקבלת גרף, שורש, וקבוצת טרמינלים ומחזירה את את המשקל המינימלי של עץ שטיינר בעומק 2 לא ניתנת לחישוב יעיל.

5. הוכיחו/הפריכו: ff ניתנת לקירוב חיבורי 7 באופן יעיל.

p_np
cook

עבור פונקציה f:NNf: \mathbb{N} \to \mathbb{N}, נגדיר מחלקת שפות NP(f)NP(f).

נאמר כי שפה LNP(f)L \in NP(f) אם קיים יחס RLR_L שהוא:

  • חסום ב-ff: לכל (x,y)RL(x,y) \in R_L מתקיים y=O(f(x))|y| = O(f(|x|)).
  • ניתן לזיהוי פולינומי: בהינתן זוג (x,y)(x,y) אפשר להכריע בזמן פולינומי אם (x,y)RL(x,y) \in R_L.
  • מגדיר את LL: L={x:y,(x,y)RL}L = \{x : \exists y, (x,y) \in R_L\}.

כלומר, ההגדרה דומה לזו של NPNP, פרט לכך שהחסם על y|y| הוא ff ולא פולינום. נסמן ב-nn את אורך הקלט.

1. הוכיחו/הפריכו: אם L1,L2NP(f)L_1,L_2 \in NP(f) אז L1L2NP(f)L_1 \cap L_2 \in NP(f)

2. הוכיחו: SATNP(n)SAT \in NP(n)

3. האם מהוכחת משפט Cook ומהסעיף הקודם אפשר להסיק כי NPNP(n)NP \subseteq NP(n)? נמקו.

4. איזו מחלקת שפות מוכרת היא NP(logn)NP(\log n)? הוכיחו.

5. הוכיחו/הפריכו: קיימת שפה LNPCL \in NPC כך ש- LNP(n1100)L \in NP(n^{\frac{1}{100}}).

model
vertex_cover

עבור מ"ט א"ד MM, נסמן ב-M\overline{M} את המ"ט המתקבלת על ידי היפוך המצבים הסופים. כלומר המצב המקבל ב-MM הוא המצב הדוחה ב-M\overline{M} וההיפך.

עבור כל אחת מהטענות הבאות קבעו האם היא נכונה, שגויה, או גוררת ש-P=NPP = NP. הוכיחו את תשובתכם.

א. לכל מ"ט א"ד פולינומית MM מתקיים L(M)=L(M)L(\overline{M}) = \overline{L(M)}.

ב. קיימת מ"ט א"ד פולינומית MM כך ש-L(M)NPL(M) \in NP וגם L(M)NPL(\overline{M}) \in NP.

ג. קיימת מ"ט א"ד פולינומית MM כך ש-L(M)NPCL(M) \in NPC וגם L(M)PL(\overline{M}) \in P.

ד. לכל מ"ט א"ד פולינומית MM מתקיים ש-L(M)PL(\overline{M}) \in P.

ה. נמקו בקצרה (יש לתאר רדוקציה אבל אין צורך להוכיח נכונות) כי השפה הבאה היא NPNP-שלמה:

}\}ב-GG יש מספר זוגי של צמתים או כיסוי בצמתים בגודל kk L1={(G,k):L_1 = \{(G,k) :

ו. נמקו בקצרה (יש לתאר רדוקציה אבל אין צורך להוכיח נכונות) כי השפה הבאה היא NPNP-שלמה:

}\}ב-GG יש מספר אי זוגי של צמתים או כיסוי בצמתים בגודל kk L2={(G,k):L_2 = \{(G,k) :

ז. קיימת מ"ט א"ד פולינומית MM כך ש-L(M)NPCL(M) \in NPC וגם L(M)NPCL(\overline{M}) \in NPC.

reduction_p_np
3col

רוצים לחלק nn אנשים ל-mm קבוצות. כל בן אדם רשאי לתת רשימה של אנשים, איתם הוא לא מעוניין להיות באותה קבוצה. צריך להכריע האם קיימת חלוקה לקבוצות כך שאף בן אדם לא נמצא בקבוצה עם מישהו שהוא לא מעוניין.

1. הראו שלא ניתן לפתור את הבעיה בצורה יעילה בהנחה ש-P̸=NPP \neq NP.

2. הראו שקיים פתרון יעיל לבעיה אם P=NPP = NP.

p_np
proof
sat

בשאלה זו φ\varphi הוא פסוק CNF, mm הוא מספר הפסוקיות ב-φ\varphi, nn מספר המשתנים ב-φ\varphi, ו-g(φ)g(\varphi) הוא מספר הפסוקיות המקסימלי שניתן לספק ב-φ\varphi על ידי השמה כלשהי.

1. בהנחה ש-P̸=NPP \neq NP קבעו האם השפה הבאה ב-PP והאם היא ב-NPNP.

}\}קיימת השמה המספקת בדיוק m2\frac{m}{2} פסוקיות H-SAT={φ:\text{H-SAT} = \{\varphi :

2. הוכיחו: אם קיימת מ"ט דטרמיניסטית פולינומית שמחשבת את g(φ)g(\varphi) אז קיימת מ"ט דטרמיניסטית פולינומית שמוצאת ל- φ\varphi השמה מספקת אם קיימת כזו, ואחרת דוחה.

3. הוכיחו/הפריכו: מכל שפה LNPL \in NP קיימת רדוקציה פולינומית ל-SAT, f(w)=φf(w) = \varphi, כך שאם wLw \in L אז g(φ)=m{g(\varphi) = m} ואם w/Lw \notin L אז g(φ)<m2g(\varphi) < \frac{m}{2}.

4. הוכיחו/הפריכו: מכל שפה LNPL \in NP קיימת רדוקציה פולינומית ל-SAT, f(w)=φf(w) = \varphi, כך שאם wLw \in L אז g(φ)=m{g(\varphi) = m} ואם w/Lw \notin L אז g(φ)=m1g(\varphi) = m - 1.

p_np
sat
approximation

בשאלה זו הניחו כי P̸=NPP \neq NP.

פסוקית 3CDNF\text{3CDNF} הנה פסוקית מהצורה ((xy)z)((x \land y) \lor z) (x,y,zx,y,z ליטרלים שונים). פסוק 3CDNF\text{3CDNF} הינו \land בין פסוקיות 3CDNF\text{3CDNF} השפה 3CD-SAT\text{3CD-SAT} הנה שפת כל פסוקי ה-3CDNF \text{3CDNF } הספיקים.

1. הוכיחו/הפריכו: 3CD-SATP\text{3CD-SAT} \in P

פסוקית 3CNF’\text{3CNF'} הנה פסוקית מהצורה ((xy)z)((x \to y) \to z) (x,y,zx,y,z ליטרלים). פסוק 3CNF’\text{3CNF'} הינו \land בין פסוקיות 3CNF’\text{3CNF'}. 3SAT’\text{3SAT'} הינה שפת כל פסוקי ה-3CNF’\text{3CNF'} הספיקים.

2. הוכיחו/הפריכו: 3SAT’P\text{3SAT'} \in P

פסוקית 3CNF-IMP\text{3CNF-IMP} הנה פסוקית מהצורה (x(yz))(x \to (y \to z)) (x,y,zx,y,z ליטרלים). פסוק 3CNF-IMP\text{3CNF-IMP} הינו \land בין פסוקיות 3CNF-IMP\text{3CNF-IMP}. 3SAT-IMP\text{3SAT-IMP} הנה שפת כל פסוקי ה-3CNF-IMP\text{3CNF-IMP} הספיקים.

3. הוכיחו/הפריכו: 3SAT-IMPP\text{3SAT-IMP} \in P

בהינתן פסוק 3CNF-IMP\text{3CNF-IMP} רוצים למצוא השמה שמספקת את המספר הגדול ביותר של פסוקיות בפסוק.

4. הוכיחו: לא קיים אלגוריתם יעיל אופטימלי לבעיה.

5. תארו אלגוריתם הסתברותי עם יחס קירוב 78\frac{7}{8} בתוחלת.

pspace
sat

נסמן L1PSL2L_1 \leq_{PS} L_2 אם קיימת פונקציה f:ΣΣf: \Sigma^* \to \Sigma^* המקיימת

  • הפונקציה ff מלאה
  • f(w)f(w) ניתנת לחישוב תוך שימוש בזיכרון פולינומי ב-w|w|
  • wL1    f(w)L2w \in L_1 \iff f(w) \in L_2

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

  1. הוכיחו: אם L2PSPACEL_2 \in \text{PSPACE} וגם L1PSL2L_1 \leq_{PS} L_2 אז L1PSPACEL_1 \in \text{PSPACE}.
  2. הוכיחו כי SATPSSAT\text{SAT} \leq_{PS} \overline{\text{SAT}}.
  3. אילו שפות LPSPACEL \in \text{PSPACE} מקיימות שלכל LPSPACEL' \in \text{PSPACE} מתקיים ש-LPSLL' \leq_{PS} L
  4. הוכיחו כי אם לכל שתי שפות L1L_1 ו-L2L_2 מתקיים ש-L1PSL2L1pL2L_1 \leq_{PS} L_2 \Rightarrow L_1 \leq_{p} L_2 אז P=PSPACE\text{P} = \text{PSPACE}.
p_np
true_false

עבור כל אחד מהסעיפים הבאים קבעו האם הוא:

  1. נכון
  2. לא נכון
  3. גורר ש-P=NP\text{P} = \text{NP}
  4. גורר ש-P̸=NP\text{P} \neq \text{NP}

1. קיימת קבוצה סופית של שפות {L1,,Lk}\{L_1, \ldots, L_k\} כך ש-LiPL_i \in P לכל ii ומתקיים iLi=SAT\bigcup_i L_i = SAT.

2. קיימת קבוצה אינסופית של שפות {L1,}\{L_1, \ldots\} כך ש-LiPL_i \in P לכל ii ומתקיים iLi=SAT\bigcup_i L_i = SAT.

3. לא קיים אלגוריתם פולינומי דטרמיניסטי הבודק עבור כל גרף GG האם קיים בו מעגל פשוט העובר דרך מחצית מהצמתים.

4. קיימות זוג שפות NP\text{NP}-שלמות L1,L2{0,1}L_1,L_2 \subseteq \{0,1\}^* עבורן L1L2PL_1 \cap L_2 \in P.

5. קיימת שפה PSPACE-שלמה השייכת למחלקה PP.

6. קיים יחס דו מקומי SS המקיים:

  • היחס חסום לוגריתמית, כלומר קיים קבוע cc, כך שלכל (x,y)S(x,y) \in S מתקיים yclog(x)|y| \leq c\log(|x|).
  • היחס ניתן לזיהוי פולינומי.
  • VC={xy,(x,y)S}VC = \{x | \exists y, (x,y) \in S\}.
p_np
independent_set

נתון מאגר של nn שאלות בחישוביות וכמו כן נתונה פונקצית דמיון בין כל זוג שאלות sim:[n]×[n]R+sim: [n] \times [n] \to \mathbb{R_+}. רוצים לכתוב מבחן עם kk שאלות, כך שסך כל הדמיון בין השאלות קטן ככל האפשר, כלומר:

minK[n]:K=ki̸=jKsim(i,j) \min_{K \subseteq [n] : |K| = k}\sum_{i \neq j \in K}sim(i, j)

1. הגדירו את הבעיה בצורה פורמלית במונחים של תורת הגרפים.

2. הראו שלא ניתן לפתור את הבעיה בצורה יעילה ואופטימלית בהנחה ש P̸=NPP \neq NP.

3. תארו אלגוריתם יעיל שמייצר מבחן עם 5 שאלות.

classification_r_re

עבור כל אחת מהשפות הבאות קבעו האם היא שייכת ל-RR והאם היא שייכת ל-RERE:

1. }\}המ"ט MM עוצרת על כל קלט תוך 1000 צעדים לכל היותר L1={M:L_1 = \{\langle M \rangle :

2. }\}קיים קבוע kk כך ש-MM עוצרת על כל קלט תוך kk צעדים לכל היותרL2={M:L_2 = \{\langle M \rangle :

3. }\}קיים פולינום PP כך ש-MM עוצרת על כל קלט, ww, תוך P(w)P(|w|) צעדים לכל היותרL3={M:L_3 = \{\langle M \rangle :

r_re

תהיינה L,L1,L2L,L_1,L_2 שפות ב-RERE. הוכיחו או הפריכו את הטענות הבאות:

  1. אם L1RL_1 \in R או L2RL_2 \in R אז L1L2RL_1 \cup L_2 \in R.
  2. אם L1L2RL_1 \cup L_2 \in R אז L1RL_1 \in R וגם L2RL_2 \in R.
  3. אם LL אינסופית וגם L\overline{L} אינסופית אז L/RL \notin R