Section 1

1.1 Exercise 1

Given a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ and a boolean circuit C of size $|C|=s$ that computes f, Lets proof that there existences of a boolean circuit $C^{\prime }$ that’s stand with the question property.

using the claim above we can intuitive say that we need to "roll down the tree" all the NOT gates, and from quick indication I can claim the following.

on the same way we proof claim 0.2 we can get the same property for the $\wedge$ gate, so in total for some $f$ we can find for any appearance of $\mathrm{\neg }$ gate $\in C$ , and each time apply De-Morgan law. based on claim 2 this new $|C^{\prime }|$ hold the property (a)(b)(c).

1.2 Exercise 2

For $f$ that has a circuit $C$ of size $m$ over $B_{\ell }$, $C$ can be written as a binary tree with $m$ internal nodes. Each internal node is labelled by a gate, and each leaf is labelled by a variable, for each $v\in C$ lets $L_v:\{0,1{\}}^k\to \{0,1\}$be the circut that accept language , according to Lupanov ’58 theorem its can be expressed as language over DeMorgan basis ,using the result of exercise 2 at Recitation 1 ,we know that for such $L_v$ language there is some $C$ that can accept it when $|C|=O(2^k)$ hence for $\mathrm{\forall }v\in C\Rightarrow M|L_v|$ can be decided with some $C_m$ size $O(m{2}^{\ell })$.

1.3 Exercise 3

$⟹$ Lets $M$ be an DFA such as $M=(Q,\sum ,\delta ,q_0,F)$ and assume that $M$ accept some $w\in \sum ^{\ast }$ i.e ${\hat{\delta }}_m(q_0,w)\in F$. using ${\hat{\delta }}_m$ definition ,lets $k_i$ be the state such as

follow same proses for $n-2,n-3,\dots$ so for general $k_i$ on the "back-word" path

hence $\mathrm{\forall }{k}_i\in Q$ , $k_n\in F$, $k_0=q_0$ and ${\delta }_m(k_{i-1},w_i)=k_i$ for $1\le i\le n$
so we can claim that the sequence $k_1,k_2,\dots k_n$ stand with the property of the second equivalent DFA definition.

$⟸$ Lets $M$ be an DFA such as $M=(Q,\sum ,\delta ,q_0,F)$ and we assume that
$\mathrm{\forall }{q}_i\in Q$ , $q_n\in F$,$w_0=q_0$ and ${\delta }_m(q_{i-1},w_i)=q_i$ for some $w=w_1,w_2,\dots w_n$ and $q_1,q_2,\dots q_n$
with the same way decribed above

in general

and we proof that both definition are equivalent

1.5 Exercise 5

Given n, Lets formalize the language

lets present NFA $N=(Q,\mathrm{\Sigma },\delta ,S,F)$ that accept $L_n$ , we know that any NFA can be transform to DFA .

Now lets show N as DFA

Question 5 (b)

1.6 Exercise 6

Let $A=(Q,\sum ,\delta ,q_0,F)$ be a DFA, and let $w_1,w_2\in {\mathrm{\Sigma }}^{\ast }$ be words such that $\hat{\delta }(q_0,w_1)=\hat{\delta }(q_0,w_2).$ Lets proof that for every word $w\in {\mathrm{\Sigma }}^{\ast }$ it holds that $w_{1}w\in L(A)\iff w_{2}w\in L(A)$ now we set some $q_k$ such as
$\hat{\delta }(q_0,w_1)=\hat{\delta }(q_0,w_2)=q_k\in Q$. now we construct new $A_1$ and $A_2$ in the following way:

we can notice that $\hat{\delta }(q_0,w_1)=\hat{\delta }(q_0,w_2)\in L(A_1)$ ,and for some $w$ such as $w\in L(A_2)$ we get

Question 6 (b)
Let n be a number and let A be a DFA such that $L(A)=\{0^i{1}^i:0\le i\le n\}.$ now follow the hint

Hence the claim above hold for any $i\ne j$ and in total we find that A has at least n accepting state.

2 Section 2

2.1 Exercise 1

Define the language $L_n$ over alphabet $\sum _n=\{1,2,...,n\}$ to be the set of words which do not contain all the letters from $\sum _n$, now lets describe DFA $M=(Q,\sum ,\delta ,q_0,F)$ s.t M accept $L_n$.

its sufficient to see that the following claim hold to proof $M$ accept $L_n$

2.2 Exercise 2

When A,B regular languages over same alphabet. $A\diamond B=\{xy:x\in A\wedge y\in B\wedge |x|=|y|\}$ lets define

by assuming that $A\diamond B$ is regular language, using the property of regular language operation we get.

which lead to contradiction since $\{0^i,1^i|i\ge 0\}$ is not regular language

2.3 Exercise 3

$\text{textbf{(a)} }{L}_1=\{w:\mathrm{\#}a(w)\ge \mathrm{\#}b(w)\}\text{ over }\mathrm{\Sigma }=\{a,b,c\}$
$L_1$ is not regular while assuming it is. for fix $\ell$ lets $w=b^{\ell }{a}^{\ell }$ ,$w\in L_1$ based on Pumping Lemma we can notice $|w|>\ell$, and for any patrion of $w=xyz$ such that $|y|>0,|xy|\le \ell$ hence y is in the form of $b^k$ now lets look at

we got an contradiction hence $L_1$ is not regular

$\text{textbf{(b)} }{L}_2=\{w:|w|\in {\mathbb{N}}_{even}\wedge w=w^R)\}\text{ over }\mathrm{\Sigma }=\{0,1\}$
$L_2$ is not regular while assuming it is. for fix $\ell$ lets $w=1^{\ell }{001}^{\ell }$ ,$w\in L_2$ based on Pumping Lemma we can notice $|w|>\ell$, and for any patrion of $w=xyz$ such that $|y|>0,|xy|\le \ell$ hence y is in the form of $1^k$ now lets look at

we got an contradiction hence $L_2$ is not regular

$\text{textbf{(c)} }{L}_3=\{w:|w|\in {\mathbb{N}}_{even}\wedge w=w^R)\}\text{ over }\mathrm{\Sigma }=\{0\}$
$L_3$ is regular language since we can be written as regular expression

$\text{textbf{(d)} }{L}_4=\{w:|w|\in \mathbb{N}\text{ s.t }|w|=n^3\}\text{ over }\mathrm{\Sigma }=\{0,1\}$
$L_4$ is not regular while assuming it is. for fix $\ell$ lets $w=0^{{\ell }^3}$ ,$w\in L_4$ based on Pumping Lemma we can notice $|xyz|>\ell$, and for any patrion of $w=xyz$ such that $|y|>0,|xy|\le \ell$. hence for some k,m such that $k+m\le \ell$ this means that :

by our assumption for any $n\in \mathbb{N},$ $x{y}^{n}z=0^{{\ell }^3+m(n-1)}\in L_4$, lets choose n=2

we got an contradiction hence $L_4$ is not regular

2.4 Exercise 4

2.5 Exercise 5

(a) Lets L be a regular language over alphabet $\mathrm{\Sigma }$. and we will proof the language $L^{\prime }$ define $L^{\prime }=\{xyz:x{y}^{R}z\in L\}$ is regular. since L is regular $\Rightarrow$ exists some DFA that accept L $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ now lets define few new DFA’s s.t:

• $M_{q_0,q_k}=(Q,\mathrm{\Sigma },\delta ,q_0,q_k)$ for any $q_k\in Q$ this DFA will cover any path that accessible from $q_0$

• now lets look at $M_{q_k,q_j}=(Q,\sum ,\delta ,q_k,q_j)$lets the language of $M_{q_k,q_j}$ is define by $L(M_{q_k,q_j})=\{w:\mathrm{\exists }{q}_k,q_j\in Q|\text{ exists path s.t }{q}_k⇝q_j\}$ ,since $L(M_{q_k,q_j})$ is regular $\Rightarrow$ $rev(L(M_{q_k,q_j}))$ is regular (Recitation 3 ex.1). for any $q_k,q_j\in Q$ lets define the following language $L(M_{q_k,q_j}{)}^R$

• $M_{q_k,F}=(Q,\mathrm{\Sigma },\delta ,q_k,F)$ for any $q_k\in Q$ this DFA will cover any path that end in $F$

(b) Lets L be a regular language over alphabet $\mathrm{\Sigma }$. and we will proof the language $L^{\prime }$ define $L^{\prime }=\{xy\in {\mathrm{\Sigma }}^{\ast }:(x\in L)\text{ XOR }(y\in L)\}$ is regular. using the closure property of regular language

• $L=\{x\in {\mathrm{\Sigma }}^{\ast }:x\in L\}$ and $\bar{L}=\{x\in {\mathrm{\Sigma }}^{\ast }:x\notin L\}$ are regular.

• $L||\bar{L}=\{xy\in {\mathrm{\Sigma }}^{\ast }:x\in L\wedge y\notin L\}$ and $\bar{L}||L=\{xy\in {\mathrm{\Sigma }}^{\ast }:x\notin L\wedge y\in L\}$ are regular.

• $(L||\bar{L})\cup (\bar{L}||L)=\{xy\in {\mathrm{\Sigma }}^{\ast }:(x\in L\wedge y\notin L)\vee (x\notin L\wedge y\in L)=(x\in L)\text{ XOR }(y\in L)\}$ is regular

Exercise 6

$\text{textbf{(a)} }\{w\in {\mathrm{\Sigma }}^{\ast }:{\mathrm{\#}}_0(w)\le 3\}$
lets express the following as regular expression

(I) is the regular expression of the language that contain non zeros at all.
(II) is the regular expression of the language that contain exactly 1 zero.
(III) is the regular expression of the language that contain exactly 2 zero.
(IV) is the regular expression of the language that contain exactly 3 zero.
hence combine them all together will hold regular expression of the language that contain at most 3 zeros.

$\text{textbf{(b)} }\{w\in {\mathrm{\Sigma }}^{\ast }:|w|\text{ mod 4}=2\}$
lets express the following as regular expression

(I) is the regular expression of the language that size is exactly 2.
(II) is the regular expression of the language from size 0,4,8..
hence the concatenate of (I) and (II) will hold the $|w|$ mod $4=2$ property

3 Section 3

3.1 Exercise 1

Considering the following language

Lets describe an 2-tape NTM $\mathcal{M}$ that allow the head to stay at the same place, that recive input $\mathrm{\#}{1}^n\mathrm{\#}(n>1)$ and implements the first part of decide $\mathcal{L}$

and define $\delta$ :

The idea behind the way I generated $\delta$ is first to verify we start "legal" sequence i.e $i\ne j$ and $i,j>0$ and split non-deterministic for any $i,j$ the NTM run

3.2 Exercise 2

(a)For DFA $A=(Q,\mathrm{\Sigma },\delta ,q_0,F)$. lets describe a 2-tape TM M that accept $\mathcal{L}(A)$

The idea is to save the last visted state on of A. (b) For TM $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$. lets describe a 2-tape TM $M_2$ that accept $\mathcal{L}(M)$

Lets define $\hat{q},\hat{\sigma },\hat{D}$ to be the triplet such that $\delta (q,\sigma )⟼(\hat{q},\hat{\sigma },\hat{D})$

The idea is kind of same as above but now we track the direction of the head of M

Exercise 3

For $L,\bar{L}$, if both are semi-decidable $\Rightarrow$ both are decidable, (can just flip the nation reject accept) $\Rightarrow$ if we assume $\mathcal{RE}$ closed under complement, $\mathrm{\forall }L\in \mathcal{RE},\bar{L}\in \mathcal{RE}\Rightarrow$ we get that $\mathcal{RE}=\mathcal{R}\Rightarrow \mathrm{♣}$

By detention $L\in co\mathcal{RE}$ if $\bar{L}\in \mathcal{RE}$. using the fact that $\mathcal{RE}$ Closures under union we can apply De-Morgan law for some $\overline{L_1},\overline{L_2}\in co\mathcal{RE}$ which lead us to :

w.l.o.g $\mathcal{L}\in \mathcal{R}$ such that exist TM $T$ that decide $\mathcal{L}$.now we can build an TM $M^{\ast }$ that accept $L^{\ast }$ for input x .

if $x=ϵ$ Accept.

partition $|x|=n$ to any combination possible ways lets say $x_{power}:=(\{x_1\},\{x_2\}\dots \{x_{2^{n-1}}\})$

run $L$ for any $\mathrm{\forall }w\in \{x_i\}$, if for some $x_i$ L accept all $w\in \{x_i\}$ Accept.

else Reject.

i. Since $\mathcal{L}\in \mathcal{RE}$, there exists an enumerator $f_{\mathcal{L}}$. Its will be sufficient to describe $f_{prefix}$ to proof that $\mathcal{L}\in \mathcal{RE}\Rightarrow \text{Prefix(}\mathcal{L})\in \mathcal{RE}$ Now lets built new $f_{prefix}$.

the idea is to use $f_{\mathcal{L}}$ output and apply Prefix on any world to create $f_{prefix}$

ii. Lets assume $\mathcal{R}$ closed under Prefix. and lets look at my favourite TM $M_F$ for $L_f\in \mathcal{RE}\mathcal{/}\mathcal{R}$. now lets construct new $\hat{L}$ consisting of strings from the encode of $M_F$ and $\mathrm{\#}$ i.e $M_F\mathrm{\#}$ now I claim that $\hat{L}$ Accept only when its see $\mathrm{\#}$ ,otherwise its Reject. hence exist some deterministic TM that Reject/Accept. $\hat{L}\in \mathcal{R}$, but Prefix($\hat{L})=L_f\notin \mathcal{R}\Rightarrow \mathrm{♣}$

3.4 Exercise 4

Define $\text{Size}(O(n))$:

i. Lets look at the unary language $\mathcal{L}\subseteq \{1^n:n\in N\}$, its immediate that $\mathcal{L}\in \text{Size}(O(n))$ since its needs to have a single “hardwired” bit for indicating $1^n$. now lets look at the language ${\mathcal{L}}_{\mathcal{U}}$

Hence its immediate from Rice’s Theorem, or the fact that $H_{TMϵ}$ ${\le }_m{\mathcal{L}}_{\mathcal{U}}$ that ${\mathcal{L}}_{\mathcal{U}}\notin \mathcal{R}$ and ${\mathcal{L}}_{\mathcal{U}}\in \text{Size}(O(n))$

ii. We can look at some recursively define $\mathcal{L}\in \mathcal{R}$ for example:

Since we will need circuit for each possible input length, we may need exponential size circuit (in terms of n) to accept words in the language. and the following holds that $\mathcal{L}\notin \text{Size}(O(n))$

3.5 Exercise 5

1. Prove: If ${\mathcal{L}}_1{\le }_m{\mathcal{L}}_2$ and ${\mathcal{L}}_2{\le }_m{\mathcal{L}}_3,$ then ${\mathcal{L}}_1{\le }_m{\mathcal{L}}_3.$
   Define $f_{1\to 2},f_{2\to 3}$ to be a computable mapping redaction functions. now lets $w\in {\mathcal{L}}_1$, and by dentition we get :

   $$w\in {\mathcal{L}}_1\iff f_{1\to 2}(w)\in {\mathcal{L}}_2\iff f_{2\to 3}(f_{1\to 2}(w))\in {\mathcal{L}}_3$$

2. Disprove: If ${\mathcal{L}}_1{\le }_m{\mathcal{L}}_2$ and ${\mathcal{L}}_2{\le }_m{\mathcal{L}}_1,$ then ${\mathcal{L}}_1={\mathcal{L}}_2.$
   for $H_{TM},A_{TM}$ we know that $H_{TM}{\le }_m{A}_{TM}$ and $A_{TM}{\le }_m{H}_{TM}$ but $A_{TM}\ne H_{TM}\Rightarrow \mathrm{♣}$

3. Disprove: If ${\mathcal{L}}_1\subseteq {\mathcal{L}}_2$ then ${\mathcal{L}}_1{\le }_m{\mathcal{L}}_2.$
   Lets look at $\mathcal{L}={\mathrm{\Sigma }}^{\ast }$,$\mathcal{L}\in \mathcal{R}$ since any other ${\mathcal{L}}^{\prime }\subseteq \mathcal{L}$. if we assume that $\mathrm{\forall }{\mathcal{L}}^{\prime }{\le }_m\mathcal{L}$ its will lead to $\mathrm{\forall }{\mathcal{L}}^{\prime }\in \mathcal{RE}\Rightarrow \mathrm{♣}$

4. Disprove: For every ${\mathcal{L}}_1,{\mathcal{L}}_2$, then ${\mathcal{L}}_1{\le }_m{\mathcal{L}}_2$ or ${\mathcal{L}}_2{\le }_m{\mathcal{L}}_1$
   Lets look at $A_{TM},\overline{A_{TM}}$. If we assume $\overline{A_{TM}}{\le }_m{A}_{TM}$ Since $\overline{A_{TM}}\notin \mathcal{RE}$ its will lead to $A_{TM}\in \mathcal{R}\Rightarrow \mathrm{♣}$,
   and if $A_{TM}{\le }_m\overline{A_{TM}}$ Since $A_{TM}\notin \text{co-}\mathcal{RE}\Rightarrow \overline{A_{TM}}\in \mathcal{R}\Rightarrow \mathrm{♣}$

5. Prove: If $\mathcal{L}$ is regular, then $\mathcal{L}{\le }_{m}HALT$
   Lets A be an DFA s.t $L(A)=\mathcal{L}$ when $\mathcal{L}$ is regular. based on 2(a) we define some TM M that accept $L(A)$ and Let $M_{loop}$ be TM that loop forever for any input. hence we can define computable f :

   $$f(w)=\{\begin{array}{ll}⟨M,w⟩& \text{if }w\in M\\ ⟨M_{loop},w⟩& \text{if }w\notin M\end{array}$$

   Which imply $\mathcal{L}{\le }_{m}HALT$

3.6 Exercise 6

Lets describe algorithm $A_{10}$ that accept $\mathcal{L}$

$A_{10}$ on input $⟨M⟩$ $⟨M⟩$ is a valid encode of TM
else Reject $k$ $\leftarrow$ 1 $k<\mathrm{\infty }$ counter $\leftarrow$ 0 $i$ $\leftarrow$ 1 to $k$ simulate $M$ on $w_i$ for $k$ steps$w_i$ generated from $\mathrm{\Sigma }$ of $M$ $M$ acceptcounter + 1 counter $>10$ Accept
Its implement that we cover any optional input on $M$ and while discovered more then 10 worlds in $\mathcal{L}$ we accept. hence $\mathcal{L}\in \mathcal{RE}$
Now lets proof $\mathcal{L}\notin \mathcal{R}$ using reduction from HALT${\le }_m\mathcal{L}$. now lets define $\mathcal{M}$ $\mathcal{M}$ on input $⟨M,\hat{w}⟩$ . $⟨M,\hat{w}⟩$ is a valid encode of TM and word
else Reject Ignore $\hat{w}$ Write $M$ and $w$ on the tape run $M$ on $w$ Accept if $M$ halt
else Reject
I claim that exists maping function from $H_{TM}$ to $\mathcal{L}$ s.t:

If $⟨M,\hat{w}⟩\in H_{TM}\Rightarrow M(\hat{w})$ halt $\Rightarrow \mathcal{M}$ accept any input $\Rightarrow |L(\mathcal{M})|>10\Rightarrow \mathcal{M}\in \mathcal{L}$

If $⟨M,\hat{w}⟩\notin H_{TM}\Rightarrow M(\hat{w})$ not halt $\Rightarrow \mathcal{M}$ dont accept any input $\Rightarrow |L(\mathcal{M})|<10\Rightarrow \mathcal{M}\notin \mathcal{L}$

Where ${\mathcal{M}}_{favourite}$ is my favourite TM that hold $|L({\mathcal{M}}_{favourite})|=10$

Lets look at

since we know that ${\mathcal{L}}_{1\wedge \mathrm{\neg }2}\in \overline{\mathcal{RE}\cup \text{co-}\mathcal{RE}}$ we can can apply mapping reduction. Now lets construct a TM ${\mathcal{M}}_{1\wedge \mathrm{\neg }2}$ that work as follow:

${\mathcal{M}}_{1\wedge \mathrm{\neg }2}$ on input $w$. If $w=0$ Then simulate $M_2$ on $w_2$ If $w=1$ Then simulate $M_1$ on $w_1$
If $w\ne 0\wedge w\ne 1$ Accept
I claim that exists maping function $f$ from ${\mathcal{L}}_{1\wedge \mathrm{\neg }2}$ to $\mathcal{L}$ s.t:

where ${\mathcal{M}}_0$ is some TM that accept 0

If $⟨M_1,w_1,M_2,w_2⟩\in {\mathcal{L}}_{1\wedge \mathrm{\neg }2}\Rightarrow w_1\in L(M_1)\wedge w_2\notin L(M_2)$
$\Rightarrow 1\in L({\mathcal{M}}_{1\wedge \mathrm{\neg }2})\wedge 0\notin L({\mathcal{M}}_{1\wedge \mathrm{\neg }2})\Rightarrow ⟨{\mathcal{M}}_{1\wedge \mathrm{\neg }2}⟩\in \mathcal{L}$

If$⟨M_1,w_1,M_2,w_2⟩\notin {\mathcal{L}}_{1\wedge \mathrm{\neg }2}\Rightarrow w_1\in L(M_1)\downarrow w_2\notin L(M_2)$
$\Rightarrow 1\in L({\mathcal{M}}_{1\wedge \mathrm{\neg }2})\downarrow 0\notin L({\mathcal{M}}_{1\wedge \mathrm{\neg }2})\Rightarrow ⟨{\mathcal{M}}_{1\wedge \mathrm{\neg }2}⟩\notin \mathcal{L}$

Lets describe an algorithm $\mathcal{A}$ that reject for $\mathcal{L}$

$\mathcal{A}$ on input $⟨M_1,M_2⟩$ $k$ $\leftarrow$ 1 $k<\mathrm{\infty }$ $i$ $\leftarrow$ 1 to $k$ simulate $M_1$ and $M_2$ on $w_i$ for $k$ steps If both accept then Reject
Hence its hold that if both $M_1,M_2$ accept same word then $\mathcal{L}(M_1)\cap \mathcal{L}(M_2)\ne \mathrm{\varnothing }$, $\mathcal{L}\in \text{co-}\mathcal{RE}$.
Now lets proof $\mathcal{L}\notin \mathcal{R}$ using reduction from $E_{TM}{\le }_m\mathcal{L}$. and its will be sufficient to see that $\overline{E_{TM}}{\le }_m\bar{\mathcal{L}}$ now lets define ND-TM ${\mathcal{M}}_E$
${\mathcal{M}}_E$ on input $⟨\hat{M}⟩$ . Guess $w$ from ${\mathrm{\Sigma }}^{\ast }$ Simulate non-deterministic $M$ on $w$
And let define $f$ s.t:

Where ${\mathcal{M}}_{ACC}$ is TM that accept any input, and ${\mathcal{M}}_{\mathrm{\varnothing }}$ is TM that don’t accept any word.

If $⟨M⟩\in \overline{E_{TM}}\Rightarrow \mathcal{L}(M)\ne \mathrm{\varnothing }\Rightarrow {\mathcal{L}\mathcal{(}\mathcal{M}}_E)\cap {\mathcal{L}\mathcal{(}\mathcal{M}}_{ACC})\ne \mathrm{\varnothing }\Rightarrow ⟨{\mathcal{M}}_E,{\mathcal{M}}_{ACC}⟩\in \bar{\mathcal{L}}$

If $⟨M⟩\notin \overline{E_{TM}}\Rightarrow \mathcal{L}(M)=\mathrm{\varnothing }\Rightarrow {\mathcal{L}\mathcal{(}\mathcal{M}}_E)\cap {\mathcal{L}\mathcal{(}\mathcal{M}}_{ACC})=\mathrm{\varnothing }\Rightarrow ⟨{\mathcal{M}}_E,{\mathcal{M}}_{ACC}⟩\notin \bar{\mathcal{L}}$.

(d) $\mathcal{L}=\{⟨M_1,M_2⟩:M_1,M_2$ are TMs and $\mathcal{L}(M_1)\subseteq \mathcal{L}(M_2)\}\in \overline{\mathcal{RE}\cup \text{co-}\mathcal{RE}}$

Lets look at

$$EQ=\{⟨M_1,M_2⟩:\text{are TMs and }\mathcal{L}(M_1)=\mathcal{L}(M_1)\}$$

Since we know that $EQ\in \overline{\mathcal{RE}\cup \text{co-}\mathcal{RE}}$ we can can apply mapping reduction $EQ{\le }_m\mathcal{L}$. Now lets construct a TM ${\mathcal{M}}_{EQ}$ that work as follow:

${\mathcal{M}}_{EQ}$ on input $⟨M_1,M_2⟩$ . Run $M_{\mathcal{L}}⟨M_1,M_2⟩$we assume that exist some TM $M_{\mathcal{L}}$ that halt $M_{\mathcal{L}}$ reject Reject $M_{\mathcal{L}}$ accept simulate $M_{\mathcal{L}}⟨M_2,M_1⟩$ Answer like $M_{\mathcal{L}}⟨M_2,M_1⟩$
We can see that ${\mathcal{M}}_{EQ}$ decides $EQ$, since ${\mathcal{M}}_{EQ}$ accept $\iff \mathcal{L}(M_1)\subseteq \mathcal{L}(M_2)\wedge \mathcal{L}(M_2)\subseteq \mathcal{L}(M_1)$. from the way we construct ${\mathcal{M}}_{EQ}$ its guaranteed that will act like any ${\mathcal{M}}_{\mathcal{L}}$ we plug in (halt/loop). Hence if we assume ${\mathcal{M}}_{EQ}$ halt and accept $\Rightarrow EQ\in \mathcal{R}$. on the other hand if we assume ${\mathcal{M}}_{EQ}$ halt and reject $\Rightarrow EQ\in \text{co-}\mathcal{RE}$
both lead to contradiction $\mathrm{♣}$

4 Section 4

4.1 Exercise 1

(a)

If $x\in \mathcal{L},$ then there exists $c\in {\mathrm{\Sigma }}^{\ast }$ such that $V$ accept $(x,c)$

If $x\notin \mathcal{L},$ then $V$ rejects $(x,c)$ for every $c\in {\mathrm{\Sigma }}^{\ast }$

If $x\in \mathcal{L},$ then there exists $c\in {\mathrm{\Sigma }}^{\ast }$ such that $V$ accept $(x,c)$

If $x\notin \mathcal{L},$ then $V$ $does$ $not$ $accept$ $(x,c)$ for every $c\in {\mathrm{\Sigma }}^{\ast }$

I $\Rightarrow$ II first property hold since its identical. and the second since when $V$ reject $(x,c)$ $\Rightarrow$ $V$ $does$ $not$ $accept$ $(x,c)$.
II $\Rightarrow$ I Let $V_{\mathbf{\text{II}}}$ define a verifier. to prove that for some $\mathcal{L}$ exists a verifier by I, its sufficient ¹ to prove that $\mathcal{L}\in \mathcal{RE}$. now lets define TM that run as follow.

${\mathcal{M}}_{\mathcal{L}}$ on input $x$ Let $c_1,c_2\dots$ denote lexicographic order for $\mathrm{\forall }c\in {\mathrm{\Sigma }}^{\ast }$ $i$ $\leftarrow$ 1 $i<\mathrm{\infty }$ $j$ $\leftarrow$ 1 to $i$ simulate $V_{\mathbf{\text{II}}}(x,c_j)$ for $i$ steps Accept if $V_{\mathbf{\text{II}}}(x,c_j)$
Let $x\in \mathcal{L}$ exists $V$ s.t $V$ accept $(x,c)\Rightarrow {\mathcal{M}}_{\mathcal{L}}$ halt and accept at some point. and If $x\notin \mathcal{L}$ then ${\mathcal{M}}_{\mathcal{L}}$ $does$ $not$ $accept$ matter how many steps we run. Hence $L({\mathcal{M}}_{\mathcal{L}})=\mathcal{L}$

(b)

If $x\in \mathcal{L},$ then there exists $c\in {\mathrm{\Sigma }}^{\ast }$ such that $V$ accept $(x,c)$

If $x\notin \mathcal{L},$ then $V$ rejects $(x,c)$ for every $c\in {\mathrm{\Sigma }}^{\ast }$

$V$ $always$ $halt$

III $\Rightarrow$ I is trivial, since its weaker condition.

I $\Rightarrow$ III Let $V$ define a verifier for some $\mathcal{L}$,same as above by Def 1 its following that $\mathcal{L}\in \mathcal{RE}$, and let $M_{\mathcal{L}}$ define some TM that accept it. we can write the following:

$$\mathcal{L}=\{x:\mathrm{\exists }c\text{ such that }(x,c)\in L(V)\}$$

where V has the property that given input $(x,c),V$ reject any input if $x\notin \mathcal{L}$ .

$V_{III}$ on input $(x,c)$ If (x,c) is invalid input then Reject Emulate in parallel $M_{\mathcal{L}}(x)$ and $V(x,c)$ Accept if $M_{\mathcal{L}}$ accept Reject if $V$ Reject
By the we define the verifier if $x\in \mathcal{L}$ $M_{\mathcal{L}}$ halt and accept. and if $x\notin \mathcal{L}$ then $V$ reject any input i.e halt and reject . Hence $V$ $always$ $halt$

4.2 Exercise 2

Let $\mathcal{C}\subset \mathcal{RE}$ be such that $\mathrm{\varnothing }\in C$. then

$${\mathcal{L}}_{\mathcal{C}}=\{⟨M⟩:M\text{ is a TM and }\mathcal{L}(M)\in \mathcal{C}\}\notin \mathcal{RE}$$

Since $\mathcal{C}\subset \mathcal{RE}$ then exist some ${\mathcal{L}}^{\prime }\in \mathcal{RE}$ such that ${\mathcal{L}}^{\prime }\notin \mathcal{C}$. Let $M_{{\mathcal{L}}^{\prime }}$ denote TM that accept ${\mathcal{L}}^{\prime }$

5 Section 5

5.1 Exercise 1

Assuming $P\ne NP$

1. Input: Sets $A_1,...,A_n$, and a number $k$.
   Question: do there exist $k$ mutually disjoint sets $A_{i1},...,A_{ik}$
   not in $\mathcal{P}$

   Proof ▼

   we can reduce IS ${\le }_P$ MDS as follow. let $G(V,E)$ denote an instant of IS problem, for any $v_i\in V$ generate set $A_i$ that contain all edges that have an end in $v_i$ i.e $v_i{v}_j\in A_i\iff v_i{v}_j\in E$. Its immediate that there is IND-SET $v_{i1},...,v_{ik}$ size k in $G$ iff there exist $k$ mutually disjoint sets $A_{i1},...,A_{ik}$. The reduction $f$ is poly-time computable function in $O(|V|+|E|)$, since we just need travel on $G$ and add the elements to the sets as described above. Additionally, given a sets, we can verify if they are disjoint and there are at least $k$ of them in poly time. Hence MDS$\notin P$

2. Input: Sets $A_1,...,A_n$.
   Question: do there exist 3 mutually disjoint sets $A_i,A_j,A_k$
   in $\mathcal{P}$

   claim

   $3$IND ² $\in \mathcal{P}$

   Proof ▼

   First notice 3IND$\in NP$ using same verifier of IS. Given $G(V,E)$ denote $|V|=n,|E|=m$ we can label its vertex $1\dots n$. run STCON on $⟨G,v_i,v_j⟩$ for any $i,j$ .now by choose any triplet from $\{1\dots n{\}}^3$ and check if STCON$⟨G,v_i,v_j⟩$ return 0 for any $i,j\in \{i,j,l\}$ in total we run $(\genfrac{}{}{0ex}{}{n}{2})$ times STCON save result on the tape size $(\genfrac{}{}{0ex}{}{n}{2})$ and check the nation for any triplet in total $(\genfrac{}{}{0ex}{}{n}{3})$. all the following is can be compute in poly time. hence 3-IND$\in$P

   Hence using same reduction described in (a) its holds that $3-$IND${\le }_{P}3-$MDS.
   

3. Input: Sets $A_1,...,A_n$, and a number $k$.
   Question: do there exist $k$ sets such that $A_{i1},...,A_{ik}$ such that $A_i\cap A_j\ne \mathrm{\varnothing }$
   not in $\mathcal{P}$

   Proof ▼

   we can reduce CLIC ${\le }_P$ Q${}_{(c)}$ as follow. let $G=(V,E)$ denote an instant of CLIC problem. using same proses as described at (a) we generate the sets $A_{vi},...,A_{vn}$. Hence if $G$ have clic size $k$ then exists $v_1\dots v_k$ s.t $(v_1{v}_2)(v_2,v_3)\dots (v_{k-1}{v}_k)\in E\iff$ for any $e=v_i{v}_j$ exists $x\in A_i,A_J$ $\iff$ $A_i\cap A_j$ for any $i\ne j$.

4. CNF${}_{50v}$
   Input: a CNF formula $\psi$ with at most 50 variables.
   Question: does there exist an assignment that satisfies $\psi$
   in $\mathcal{P}$

   Proof ▼

   Let $\mathcal{A}$ denote algorithm that get as input CNF formula $\psi$. If $\psi$ contain more then 50 variables then $\mathcal{A}$ immediately reject, otherwise its "brute force" by set any possible combination of boolean assignment for the given variables, If one of them satisfy $\psi$ its ACCEPT, and if none of them satisfy $\psi$ then REJECT. Since from 50 variables there are total of $2^{50}$ possible assignment, $\mathcal{A}$ is polynomial algorithms that decide our problem.

5. Input: a CNF formula $\psi$ with at most 50 clauses.
   Question: does there exist an assignment that satisfies $\psi$
   in $\mathcal{P}$

   Proof ▼

   Let $\psi$ be a CNF formula with at most 50 clauses on $n$ literals. Consider some algorithm $\mathcal{A}(\psi )$ that try all possible ways to choose one literal from each clause whenever $x_i,\mathrm{\neg }{x}_i$ does Not appear together $\mathrm{\forall }i$. If $\mathcal{A}$ find such an assignment $\Rightarrow \psi$ satisfies, otherwise it is not .Since there are at most $(2n{)}^{50}$ ways to choose such an assignment, $\mathcal{A}$ is polynomial algorithms that decide our problem.

6. Input: a 3CNF formula $\psi$ with even number of variables.
   Question: does there exist an assignment that satisfies $\psi$ and gives $True$ for exactly one half of the variables?
   not in $\mathcal{P}$

   Proof ▼

   we can reduce 3SAT ${\le }_P$ 3CNF${}_{half}$ as follow. Given 3SAT formula $\psi$ that have $n$ variable $x_1\dots x_n$, now construct new $n$ variable $y_1\dots y_n$ such that each $y_i$ correspond to the opposite value of $x_i$, its can done by adding to $\psi$ 2-CNF clauses i.e

   $$(x_1\vee y_1)(\overline{x_1}\vee \overline{y_1})\dots (x_n\vee y_n)(\overline{x_n}\vee \overline{y_n})$$

   Any solutions to the formula will have half the variables with true values and half false. the following can done in poly-time with computable function just duplicate $\psi$ variables and add the 2-CNF clauses.

7. Input: undirected graph $G$, a number $k$.
   Question: does there exist in $G$ a clique of size at least $k$ or an independent set of size at least $k$?
   not in $\mathcal{P}$

   Proof ▼

   we can reduce IS ${\le }_P$ CLIC$\vee$IS as follow. let $G=(V,E)$ instant of IS problem, we can construct new graph $G^{\prime }$ by adding set of additional $|V^{\prime }|=|V|$ isolated vertexes. now define

   $$f(⟨G=(V,E),k⟩)=⟨G^{\prime }=(V+V^{\prime },E),k+|V|⟩$$

   $f$ is polynomial. Since $k+|V|>|V|$ then $G^{\prime }$ don’t have CLIC size $k+|V|$ for sure. and exist IS size $k$ in $G$ $\iff$ exist IS size $k+|V|$ in $G^{\prime }$. Hence CLIC$\vee$IS $\notin$P

5.2 Exercise 2

1. For every nontrivial $L_1,L_2\in P,L_1\le L_2$
   TRUE

   Let $L_1,L_2\in P$ W.L.O.G we can generate arbitrary $f$ that yield $L_1{\le }_P{L}_2$

   $f$ on input $w$ . Decide $w\in L_1$ If $w\in L_1$ Return any $w^{\prime }\in L_2$ If $w\notin L_1$ Return any $w^{″}\notin L_2$
   First line can done in poly-time since $L_1\in P$, 2${}^{\text{nd}}$ holds because $L_2\ne \mathrm{\varnothing }$ and 3${}^{\text{nd}}$ since $L_2\ne {\mathrm{\Sigma }}^{\ast }$. All the following can done in poly-time hence $f$ poly-time computable reduction function from $L_1{\le }_P{L}_2$
   

2. For every nontrivial $L_1,L_2\in NP,L_1{\le }_P{L}_2$
   Equivalent to an Open Problem

   claim

   $P=NP$ $\iff$ claim $2(b)$ is True

   Proof ▼

   $\Rightarrow$ if $P=NP$ any $L_1,L_2\in NP\Rightarrow L_1,L_2\in P\Rightarrow$ Using 2(a) any non-trivial $L_1,L_2\le P$ can reduce to any other $\Rightarrow L_1{\le }_p{L}_2$ claim 2(b) Is true.
   
   $\Leftarrow$ Consider some non trivial $L_2\in P$, and assume that exist non trivial $L_1\in NP/P$. Since $P\subseteq NP$ then $L_2\in NP\Rightarrow$ claim 2(b) yield that exists reduction s.t $L_1{\le }_P{L}_2$ then $L_1\in P$ but $L_1\in NP/P$ and we get an contradiction $\Rightarrow$ there is no exist such $L_1\Rightarrow NP/P=\mathrm{\varnothing }\Rightarrow NP\subseteq P\Rightarrow P=NP$

3. There exists a language in $\mathcal{RE}$ that is complete w.r.t polynomial-time reductions.
   TRUE.

   claim

   $A_{TM}$ is complete w.r.t polynomial-time reductions.

   Proof ▼

   consider $f(w)=⟨\mathcal{M},w⟩$ for any $L\in \mathcal{RE}$ and TM $\mathcal{M}$ that accept $L$. $f$ computable, and able to write the encode of $\mathcal{M},w$ in poly time. Since $w\in L\iff ⟨\mathcal{M},w⟩\in A_{TM}$, $f$ define poly-time reduction for any arbitrary $L\in \mathcal{RE}$. $A_{TM}$ is complete w.r.t polynomial-time reductions

4. If there exists a deterministic TM that decides SAT in time $n^{O(\log n)}$
   Then every $L\in NP$ is decidable by a deterministic TM in time $n^{O(\log n)}$.
   TRUE.

   Proof ▼

   Let $L\in \mathcal{NP}$ and ${\mathcal{M}}_{SAT}$ denote D-TM that decide SAT. Since $SAT\in \mathcal{NPC}$ then exist some poly-time reduction $f$ s.t $L{\le }_{P}SAT$ decide SAT. Let look at d-TM ${\mathcal{M}}^{\prime }$.

   ${\mathcal{M}}^{\prime }$ on input $w$ . Computes $f(w)$ Simulate ${\mathcal{M}}_{SAT}(f(w))$ and Answer like ${\mathcal{M}}_{SAT}$
   $w\in L\iff {\mathcal{M}}_{SAT}$ accept $f(w)\iff f(w)\in SAT$. Since $f\in \mathcal{O}(n)\Rightarrow |f(w)|=n^k$ and ${\mathcal{M}}_{SAT}\in \mathcal{O}(n^{O(\log n)})$ its following that

   $${\mathcal{M}}^{\prime }(w)={\mathcal{M}}_{SAT}(f(w))\in \mathcal{O}({\mathcal{M}}_{SAT}(n^k))=\mathcal{O}(n^k{)}^{O(\log n^k)}=\mathcal{O}(n^{O(\log n)})$$

5.3 Exercise 3

claim

if P = NP, there exists a polynomial-time TM, that given a $3$CNF formula $\psi$ , outputs a satisfying assignment for $\psi$ or indicates one does not exists.

Proof ▼

first notice that if $P=NP$ then $NP\subseteq P$, since $3CNF\in NP$ then $3CNF\in P$. Its following that exist polynomial-time TM ${\mathcal{M}}_{3CNF}$ that decide 3CNF. Now let us define TM ${\mathcal{M}}^{\prime }$ that given a formula $\psi =\alpha (x_1,x_2\dots x_N)$ work such that:

${\mathcal{M}}^{\prime }$ on input $\psi$ . check if $\psi$ is valid 3CNF formula, otherwise Reject Simulate ${\mathcal{M}}_{3CNF}⟨\psi ⟩$ and Reject if ${\mathcal{M}}_{3CNF}⟨\psi ⟩$ Reject $\alpha (x_1,x_2\dots x_N)\leftarrow \psi$$\alpha$ represent the logic relation w.r.t $\psi$ $y_j\leftarrow 01\le j\le N$ $i\leftarrow 1$ $i\le N$ Simulate ${\mathcal{M}}_{3CNF}⟨\alpha (y_1,y_2\dots y_{i-1},T,x_{i+1}\dots x_N)⟩$ ${\mathcal{M}}_{3CNF}$ Accept$y_i\leftarrow T$ ${\mathcal{M}}_{3CNF}$ reject $y_i\leftarrow F$ $\alpha (x_i)\leftarrow y_i$ output $y_i\dots y_N$
If $\psi$ does not have an boolean satisfy assignment then ${\mathcal{M}}^{\prime }$ indicate that at step 2. The correctness of ${\mathcal{M}}^{\prime }$ following from the "greedy" posses, i.e before any iteration $\alpha$ can be satisfied. Hence by assign each time one of the veritable to T, we check if ${\mathcal{M}}_{3CNF}$ accept. if its accept the assignment its satisfied, and if its reject then the value $F$ is the valid assignment. ${\mathcal{M}}^{\prime }$ run $N+1\times {\mathcal{M}}_{3CNF}$ that is poly-time TM that output a satisfying assignment for $\psi$ or indicates one does not exists.

5.4 Exercise 4

We say that a polynomial reduction $f$ is a $shrinking$ $reduction$ if there exists $n_0$ such that for every $x\in {\mathrm{\Sigma }}^{\ast }$ such that $n_0\le x,|f(x)|\le |x|-1$. Assuming $P\ne NP$

1. For every two nontrivial languages $A,B\in P$ there exists a $shrinking$ $reduction$ from A to B.
   Prove

   Proof ▼

   using Q2(a) between any non trivial $A,B\in P$ exists mapping reduction. Since both non trivial, then exists some $b\in B,\bar{b}\notin B$. Consider $f$ s.t

   $$f(w)=\{\begin{array}{ll}b& \text{if }w\in A\\ \bar{b}& \text{if }w\notin A\end{array}$$

   Its immediate that $f(w)\in B\iff f(w)=b\iff w\in A$. and $f$ define valid poly- reduction. Let us define $n_0=max\{|\bar{b}|,|b|\}+1$, we can notice that $f$ define $shrinking$ $reduction$ from A to B since

   $$x\in {\mathrm{\Sigma }}^{\ast }\text{ s.t }{n}_0\le |x||f(x)|\le max\{|\bar{b}|,|b|\}\le n_0-1\le |x|-1$$

2. For every two nontrivial languages $A,B\in NPC$ there exists a $shrinking$ $reduction$ from A to B.
   Disprove
   

   Proof ▼

   let $A$ be any non trivial language s.t $A\in NPC$. By consider the following claim is true, W.L.O.G we can choose $A=B$. then exist $shrinking-reduction$ $f$ with some $n_0$ such that $A{\le }_{P}A$. First notice that there is only finite many $w$ s.t $|w|<n_0$. We can encode them all correct answers to an algorithm $\mathcal{A}$. For given $x\in {\mathrm{\Sigma }}^{\ast }$ if $|x|<n_0$ then its encoded already to $\mathcal{A}$. Since $f(x)<|x|$, when $|x|\ge n_0$ we can apply finite time of $ff\dots (x)$ until we achieve some $|w|<n_0$. All can done in poly-time since $f$ is poly-reduction. Hence $\mathcal{A}$ decide any non trivial $A\in NPC$ in polynomial time, its following that $P=NP$, Contradiction.

5.5 Exercise 5

The following languages are NPC:

1. $$EXACT3SAT=\{\phi \in 3SAT:\text{every clause of }\phi \text{ has exactly 3 distinct variables}\}$$

   The verifier for SAT is valid poly-time verifier for EX-3SAT$\in NP$. We can reduce 3SAT${\le }_P$EX-3SAT. Given instant of SAT $\psi =C_1\wedge C_2\dots C_n$ for any clause $C_i$, define $f$ work as follows

   If $C=\mathrm{\varnothing }$ i.e $\psi$ have empty clause then it is unsatisfiable. then $f$ return any possible combination that can generate using 3 distinct variables i.e $2^3$ clauses of 3EX-SAT

   $$\begin{array}{rl}f(\mathrm{\varnothing })& =(x\vee y\vee z)\wedge (x\vee y\vee \mathrm{\neg }z)\wedge (x\vee \mathrm{\neg }y\vee z)\wedge (x\vee \mathrm{\neg }y\vee \mathrm{\neg }z)\wedge \\ & (\mathrm{\neg }x\vee y\vee z)\wedge (\mathrm{\neg }x\vee y\vee \mathrm{\neg }z)\wedge (\mathrm{\neg }x\vee \mathrm{\neg }y\vee z)\wedge (\mathrm{\neg }x\vee \mathrm{\neg }y\vee \mathrm{\neg }z)\end{array}$$

   $\mathrm{\varnothing }\equiv f(\mathrm{\varnothing })$

   $C=(x)$ when C have just one literal. Let us define $f$ such that

   $$f((x))=(x\vee y\vee z)\wedge (x\vee \mathrm{\neg }y\vee z)\wedge (x\vee y\vee \mathrm{\neg }z)\wedge (x\vee \mathrm{\neg }y\vee \mathrm{\neg }z)$$

   $(x)\equiv f(x)$

   $C=(x\vee y)$ when C have just 2 literal. Let us define $f$ such that

   $$f((x\vee y))=(x\vee y\vee z)\wedge (x\vee y\vee \mathrm{\neg }z)$$

   $(x\vee y)\equiv f((x\vee y))$

   $C=(x\vee y\vee z)$ then $f(C)=C$

   Hence let $f^{\prime }(\psi )=f^{\prime }(C_1\wedge C_2\dots C_n)=f(C_1)\wedge f(C_2)\dots f(C_n)$ define poly-time reduction from 3SAT to EX-3SAT. Following that EX-3SAT$\in NPC$

2. $$L_2=\{⟨M,1^n⟩:\text{M is a TM and there exists a string that M accepts in n steps}\}$$
   Proof ▼

   First consider some $w=⟨M,1^n⟩$ we can verify that $w\in L_2$, by simulate M on any input size $n$ that is ⁴ $n^{|{\mathrm{\Sigma }}^{\ast }|}\in \mathcal{O}(n)$, and in total $\mathcal{O}(n^{|{\mathrm{\Sigma }}^{\ast }|}|M{|}^{3}n\log n)\Rightarrow L_2\in NP$
   Let $L$ be any $L\in NP$, and $V_L$ denote its polynomial verifier, and assume its runtime is $p(|x|)$. Any such $L$ can reduce $L{\le }_P{L}_2$ as follows

   $$x\in L\iff \mathrm{\exists }c\text{s.t }(x,c)\in V_L\iff f(x)=⟨V_L,1^{p(|x|)}⟩\in L_2$$

   The correctness followed by the verifier definition, and $f$ define computable poly-reduction from any $L\in NP$, Hence $L_2\in NPC$

6 Section 6

6.1 Exercise 1

Let proof that

$$\overline{2SAT}{\le }_{P}PCON$$

1. We can allocate space on the working tape for counters of the variables and the assignment, and all can done in $O(\log n)$ space.

2. If $⟨G,P⟩\in PCON\Rightarrow$ exist some $(u,v)\in P$ s.t $u⇝v$ and $v⇝u\Rightarrow$ exist cycle $C\subseteq G$ such that $u,v\mathrm{\neg },u,\mathrm{\neg }v\in C$ and $v⇝\mathrm{\neg }v⇝v\in G\Rightarrow$ any $x_1\dots x_v\dots x_n$ that satisfies $\phi$ following that $x_1\dots \mathrm{\neg }{x}_v\dots x_n$ satisfies $\phi$ as well $\Rightarrow v\equiv \mathrm{\neg }v$ contradiction.

3. ⁵ If $⟨G,P⟩\notin PCON$ then $t$ is well defined, since if $v⇝\mathrm{\neg }u,v⇝u$ then by $f$ definition $v⇝u⇝\mathrm{\neg }v$. and when we looking at closure size 1 $(u)$ then both $u,\mathrm{\neg }u$ reachable as well. Hence if $⟨G,P⟩\notin PCON$ then $P⊈G\Rightarrow$ for any $u,v$ exist $e$ s.t $e\in (V\times V),e\notin E$ $t(v)=1$ then $v⇝̸\mathrm{\neg }v$ for any $v\in G$. then $\mathrm{\forall }{\ell }_1\in \phi$ we get that $t(\ell )⨁t(\mathrm{\neg }\ell )=1$. and we can consider it as

   $$t=(t({\ell }_1)⨁t(\mathrm{\neg }{\ell }_1))\vee (t({\ell }_2)⨁t(\mathrm{\neg }{\ell }_2))\dots$$

   And its immediate that t satisfies $\phi$

6.2 Exercise 3

$ZPP\subseteq RP\cap coRP$

Proof ▼

Let $\mathcal{L}\in ZPP\Rightarrow$ there exists an expected poly-time TM $\mathcal{M}$ that decides $\mathcal{L}$
using Markov’s inequality $Pr(x\ge a)\le \frac{E[x]}{a}\le \frac{p(|x|)}{a}\Rightarrow Pr(x\ge 2p(|x|))\le \frac{1}{2}$
Let describe an algorithm $A_{RP}$ on input $x$

$A_{RP}$ on input $x$ Simulate $\mathcal{M}(x)$ for at most $2p(x)$ steps. If $\mathcal{M}(x)$ halt answer like $\mathcal{M}(x)$ Otherwise Reject
Its immediate that $A_{RP}$ always reject for $x\notin L$, and by the ineq above $A_{RP}$ accept $x\in \mathcal{L}$ with probability $\ge 1/2$, hence $ZPP\subseteq RP$. using same algorithm described above with flip the nation in line 3 from Reject to Accept, will give us same result for $coRP$.