Section 1

1.1 Exercise 1

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

claim 1.1

Any simple logic statement that uses $\vee $ or $ \wedge $ before $ \neg $ can be re-form to $\neg $ before $\vee $ or $ \wedge $ using one additional gate

Proof ▼

using De-Morgan law for $ x,y \in \lbrace 0, 1\rbrace $ : $\neg (x \vee y)$= $ \neg x \wedge \neg y$ and on the same way for $\neg (x \wedge y)$= $ \neg x \vee \neg y$, we apply the same statement using extra one gate in total.

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.

claim 1.2

if $P$ have some cycle $C$ size $K$ that compute it $\Rightarrow $ three is some cycle $|C'|= |2K-1|$ that can computes $P$ where all the $\neg $ gate’s before any $ \wedge $ or $\vee $ gates

Proof ▼

the indication base case is given from claim0.1, so for some Atomic $P$ where $P_i \in \lbrace 0, 1\rbrace \Rightarrow $ in total $|K|$ simple gates we get:

\[ \neg (P_1 \vee P_2 \vee \dots P_n)\Rightarrow \neg P_1 \wedge \neg P_2 \wedge \dots \neg P_n \]

we can notice that now we need $|K|$ NOT gates and$|K-1|$ of $\wedge $ gates, and in total $|K+K-1|$ gates. and all the $\neg $ gate’s before any $ \wedge $ gate’s.
Now lets $P_k$ be any boolean function that stand with the induction property,for some $x,y \in \lbrace 0, 1\rbrace $ lets look at:

\[ X=\neg (P_k\vee x)= \neg P_K \wedge \neg x, Y=\neg (P_k\wedge y)= \neg P_K \vee \neg y \]

so in any case $X,Y$ can be written in $|2k-1|$ gates of $P_k$, additional NOT gate and one $\wedge $ or $\vee $ gate, in total $|2k-1+3|=|2k+2|$ under the induction assumption we know that $P$ have some $|C|=K$ that compute it ,so $C$ including the following $ \neg , \vee $ witch is size $|K+3|$ and can compute X

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 $\neg $ gate $\in C$ , and each time apply De-Morgan law. based on claim 2 this new $|C'|$ 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: \lbrace 0, 1\rbrace ^k \rightarrow \lbrace 0, 1\rbrace $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 $\forall v \in C \Rightarrow M|L_v|$ can be decided with some $C_m$ size $O(m2^\ell )$.

1.3 Exercise 3

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

\[ \ \hat{\delta }_{m} (q_0,w)=k_{n} \]

\[ \ \hat{\delta }_{m} (q_0,w)=\delta (\hat{\delta }_{m} (q_0,w_1,w_2\dots w_n-1),w_n)\Rightarrow k_{n-1}=\hat{\delta }_{m} (q_0,w_1,w_2\dots w_n-1) \]

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

\[ \ \hat{\delta }_{m} (q_0,w_j)=\delta (\hat{\delta }_{m} (q_0,w_1,w_2\dots w_{j-1}),w_j)\Rightarrow k_{j-1}=\hat{\delta }_{m} (q_0,w_1,w_2\dots w_{j-1}) \]

hence $\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 \leq i \leq 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.

$\Longleftarrow $ Lets $M$ be an DFA such as $M=(Q,\sum ,\delta ,q_0,F)$ and we assume that
$\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

\[ \ \delta (q_0,w_1)=q_1,\hat{\delta _m}(q_0,w_1,w_2)=\delta ( \delta (q_0,w_1),w_2)=\delta ( q_1,w_2)=q_2, \]

in general

\[ \ \hat{\delta _m}(q_0,w_1,\dots ,w_j)=\delta ( \hat{\delta _m} (q_0,w_1,\dots ,w_{j-1}),w_j)=q_j \]

\[ \ \hat{\delta _m}(q_0,w_1,\dots ,w_n)=\delta ( \hat{\delta _m} (q_0,w_1,\dots ,w_{n-1}),w_n)=q_n \in F \]

and we proof that both definition are equivalent

1.5 Exercise 5

Given n, Lets formalize the language

\[ L_n=\lbrace w0w_n | w \in \lbrace 0,1\rbrace ^* \wedge w_n \in \lbrace 0,1\rbrace ^{n-1} \rbrace \]

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

\[ Q=\lbrace q_0,q_1\dots ,q_{n} \rbrace ,\Sigma =\lbrace 0,1\rbrace ,S =\lbrace q_0\rbrace ,F =\lbrace q_{n}\rbrace \]

\[ \delta (q_i,\sigma ) = \begin{cases} \lbrace q_0,q_1 \rbrace & \quad \text{if } q_i=q_0 \wedge \sigma =0 \\ \lbrace q_0 \rbrace & \quad \text{if } q_i=q_0 \wedge \sigma =1 \\ \lbrace q_{i+1} \rbrace & \quad \text{if } 0{\lt}q_{i}{\lt}q_n \forall \sigma \in \Sigma \\ \phi & \quad \text{if } q_i=q_n \forall \sigma \in \Sigma \\ \end{cases} \]

claim 1.3

N accept $L_n$

Proof ▼

$w \in L_n \Leftrightarrow $

\[ w \in \lbrace w0w_n | w \in \lbrace 0,1\rbrace ^* \wedge w_n \in \lbrace 0,1\rbrace ^{n-1}\rbrace \Leftrightarrow \exists \hat{w} \in \Sigma ^*.\exists \sigma \in \lbrace 0\rbrace .w_n \in \lbrace 0,1\rbrace ^{n-1} \]

\[ \Leftrightarrow \exists \hat{w} \in \Sigma ^*.\exists \sigma \in \lbrace 0\rbrace .\hat{\delta }_w(q_1,w_{n})\in Q \Leftrightarrow \exists \hat{w} \in \Sigma ^*.\exists \exists \delta (q_0,q_1) ,\hat{\delta }_w(q_1,w_{n}))\in Q \]

\[ \Leftrightarrow \exists \hat{w} \in \Sigma ^*.\exists \hat{\delta }(q_0,q_n)\in Q \Leftrightarrow \exists \exists \dots q_i,q_j\in Q.\exists \hat{\delta }(q_0,q_n)\in F \]

\[ \Leftrightarrow \delta (\hat{\delta }_w(q',q_n),\sigma )\exists q' \in Q \forall \sigma \in \Sigma .\hat{\delta }(q_0,q_n)\in F \Leftrightarrow \phi .(q_0,q_n)\in F \Leftrightarrow (q_0,q_n)\in L(N) \]

to be honest i’m not relay sure about the last few equivalence :)

Now lets show N as DFA

\[ Q_m=\lbrace [R]|R \in Q \rbrace ,\Sigma =\lbrace 0,1\rbrace ,\delta _0 = q_0 ,F_m =\lbrace [R]|R \cap Q \neq \phi \rbrace ,\delta _m([R],\sigma ) =\cup _{q \in R} \delta (q,\sigma ) \]

Question 5 (b)

claim 1.4

All regular languages is closed under $\backslash $ with a any regular language.

Proof ▼

Lets $L_1$ and $L_2$ be regular, using the regular opertor we know already, we can immediately claim that following holds

\[ L_1 \cap \overline{L_2} \Rightarrow L_1\backslash L_2 \text{ is regular language} \]

1.6 Exercise 6

Let $A=(Q,\sum ,\delta ,q_0,F)$ be a DFA, and let $w_1,w_2 \in \Sigma ^*$ be words such that $\hat{\delta }(q_0, w_1) = \hat{\delta }(q_0, w_2).$ Lets proof that for every word $ w \in \Sigma ^*$ it holds that $w_1w \in L(A) \Leftrightarrow w_2w \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:

\[ A_1=(Q,\Sigma ,\delta ,q_0,q_k=F_1), A_2=(Q,\Sigma ,\delta ,q_k,F_2=F) \]

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

\[ w \in L(A_2) \Leftrightarrow \hat{\delta }(q_k, w) \in F_2 \Leftrightarrow \hat{\delta }(q_k, w) \in F \]

\[ \Leftrightarrow q_k \in F_1, \hat{\delta }(q_k, w)\in F \]

\[ \Leftrightarrow \forall w'\in L(A_1).\hat{\delta } (\hat{\delta }(q_0,w')),w)\in F \]

\[ \hat{\delta } (\hat{\delta }(q_0,w_1)),w)\in F \Leftrightarrow \hat{\delta } (\hat{\delta }(q_0,w_2)),w)\in F \]

\[ w_1w\in L(A) \Leftrightarrow w_2w\in L(A) \]

Question 6 (b)
Let n be a number and let A be a DFA such that $L(A) = \lbrace 0^i1^i : 0 \leq i \leq n\rbrace . $ now follow the hint

claim 1.5

$\hat{\delta }(q_0,0^i) \neq \hat{\delta }(q_0,0^i) $ for any $i\neq j$

Proof ▼

lets assume that $\hat{q}=\hat{\delta }(q_0,0^i) = \hat{\delta }(q_0,0^j) $ and without any loss of generality $i{\lt}j$ .from A definition we know that $w_i:= 0^i1^i ,w_i:= 0^j1^j \in L(A)$ i.e for $\hat{\delta }(\hat{\delta }(q_0,0^j),1^i )$ we can get to for some $q\in F$. now lets look at

\[ \hat{\delta }(q_0,w)\in F \Rightarrow \ \hat{\delta }(\hat{\delta }(q_0,0^i),1^j )=\hat{\delta }(\hat{q},1^i ) \]

under the assuming we lets look at

\[ \hat{\delta }(\hat{q},1^i )=\hat{\delta }(\hat{\delta }(q_0,0^j),1^i )=\hat{\delta }(q_0,0^j1^i)\in F \]

and we got an contradiction.

Hence the claim above hold for any $i\neq 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 = \lbrace 1, 2, ..., n\rbrace $ 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$.

\[ Q=\lbrace q_k | k \subseteq \lbrace \Sigma _n \rbrace \rbrace ,\Sigma =\Sigma _n,q_0={q_{\phi }},F=\lbrace Q/\lbrace 1,2,3\dots n \rbrace \rbrace \]

\[ \delta (q_k,\sigma ) = \begin{cases} q_{k\cup \sigma } & \quad \text{if } \sigma \not\in \lbrace k \rbrace \\ q_k & \quad \text{if } \sigma \in \lbrace k \rbrace \\ \end{cases} \]

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

claim 2.1

the DFA M not accept w iff $\lbrace \sigma : \sigma \in w \rbrace =\lbrace k_n \rbrace $ when $k_n$ is the set of all the letters from $\Sigma _n$

Proof ▼

First lets notice that Q contain all the subset from $\Sigma _n$ including the empty set witch correspond the empty world i.e $\lbrace \sigma \rbrace $ so in total we looking at $O(2^n)$ state for finite alphabet size $n$.
$\Rightarrow w\notin L_m$ if $w\in \Sigma _n^*$ since M have only one state lets call it $q_n$ which is not accepting state, hence $\hat{\delta }(q_0,w)=q_n$ we must go through at least n state to achieve $q_n$.
now using reduction on the number of district steps we done for $\hat{w}=\phi $ $\delta (q_0,\phi )=q_0$ and for some $\hat{w},\hat{\sigma }$ s.t

\[ \hat{\sigma }\notin |\lbrace \sigma :\sigma \in \hat{w}\rbrace |=|k| , \hat{\delta }(q_0,\hat{w})=q_{k}\Rightarrow \delta (q_k,\hat{\sigma })=q_{k\cup \hat{\sigma }}=\hat{\delta }(q_0,(\hat{w}||\hat{\sigma })), \lbrace \sigma :\sigma \in \hat{w}||\hat{\sigma }\rbrace |=|k+1| \]

hence we done n district steps so $| \lbrace \sigma :\sigma \in w\rbrace |=n$ since M is DAG (except the self loops) w contain all the letters from the alphabet
$\Leftarrow $ $w:= \forall \sigma \in \Sigma _n |\sigma \in \lbrace w \rbrace $ now lets look at the first $\sigma \in w$, so $\delta (q_0,\sigma )=q_{\sigma }\in Q$ if the next letter in w hold $\hat{\sigma }\neq \sigma ,\delta (q_{\sigma },\hat{\sigma })=q_{\sigma }$ but we know that w have n district letters so in total we get

\[ \hat{\delta }(q_0,w)=\hat{\delta }(q_{\sigma _1},\underbrace{\hat{w}}_{\lbrace \hat{w} \rbrace =\lbrace w/ \sigma _1\rbrace })=\hat{\delta }(q_{\lbrace \sigma _1,\sigma _2\dots \sigma _k \rbrace },\underbrace{\hat{w}}_{\lbrace \hat{w} \rbrace =\lbrace w/ \sigma _1,\sigma _2\dots \sigma _k \rbrace })=\delta (q_{\lbrace w/ \sigma _n \rbrace },\sigma _n)=q_n \notin F \]

hence $w\notin L_m$.

2.2 Exercise 2

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

\[ \Sigma =\lbrace 0,1 \rbrace , A=L(0^*), B=L(1^*) \]

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

\[ (A \diamond B )\cap \lbrace 0^*,1^*\rbrace =\lbrace 0^i,1^i|i\geq 0 \rbrace \]

which lead to contradiction since $\lbrace 0^i,1^i|i\geq 0 \rbrace $ is not regular language

2.3 Exercise 3

$\text{\textbf{(a)} } L_1 = \lbrace w : \# a(w) \geq \# b(w)\rbrace \text{ over } \Sigma = \lbrace a, b, c\rbrace $
$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|{\gt}\ell $, and for any patrion of $w=xyz$ such that $|y|{\gt}0,|xy|\leq \ell $ hence y is in the form of $b^k$ now lets look at

\[ b^{\ell +k}a^{\ell }\Rightarrow \# _{b}(b^{\ell +k}a^{\ell }){\gt}\# _{a}(b^{\ell +k}a^{\ell })\Rightarrow b^{\ell +k}a^{\ell } \notin L_1 \]

we got an contradiction hence $L_1$ is not regular

$\text{\textbf{(b)} } L_2 = \lbrace w : |w| \in \mathbb {N}_{even} \wedge w=w^R )\rbrace \text{ over } \Sigma = \lbrace 0,1 \rbrace $
$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|{\gt}\ell $, and for any patrion of $w=xyz$ such that $|y|{\gt}0,|xy|\leq \ell $ hence y is in the form of $1^k$ now lets look at

\[ (1^{k+\ell }001^\ell )\neq (1^{k+\ell }001^\ell )^R\Rightarrow 1^{k+\ell }001^\ell \notin L_2 \]

we got an contradiction hence $L_2$ is not regular

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

\[ L_3=L((00)^*)=\lbrace 00\rbrace ^*=\lbrace \epsilon ,00,0000,\dots \rbrace \]

$\text{\textbf{(d)} } L_4 = \lbrace w : |w| \in \mathbb {N}\text{ s.t } |w|=n^3 \rbrace \text{ over } \Sigma = \lbrace 0,1 \rbrace $
$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|{\gt}\ell $, and for any patrion of $w=xyz$ such that $|y|{\gt}0,|xy|\leq \ell $. hence for some k,m such that $k+m\leq \ell $ this means that :

\[ x=0^k,y=0^m,z=0^{\ell ^3-k-m}\Rightarrow ,xyz=0^{\ell ^3} \]

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

\[ \text{since $1\geq m \geq \ell $ we will get for some $t$} \Rightarrow \underline{t^3=\ell ^3+m } \]

\[ \text{but } t^3\geq (\ell +1)^3=\ell ^3+3\ell ^2+3\ell +1{\gt} \ell ^3+\ell \geq \ell ^3+m\Rightarrow \underline{t^3{\gt}\ell ^3+m} \]

we got an contradiction hence $L_4$ is not regular

2.4 Exercise 4

claim 2.2

For language L s.t L satisfies pumping lemma with pumping constant $\ell $ ,
$L||L$ satisfies pumping lemma with pumping constant $2\ell $

Proof ▼

Lets $w_1,w_2\in L'$ i.e $w_1\in L \wedge w_2 \in L $ and lets assume $|w_1w_2|\geq 2\ell $ to imply the pumping lemma, now we can notice that there is 2 possible scenario

$|w_1|\geq \ell $ hence we can write $w_1$ as $w_1=xyz \Rightarrow $ and we can write $w_1w_2$ as $w_1w_2=xyz||w_2$ which stand with the lemma property
$|w_1|{\lt}\ell $ so $|w_2|{\gt}\ell $ can write $w_2$ as $w_2=xyz$ and $|xy|\leq \ell \Rightarrow |w_1xy|\leq 2\ell ,|y|{\gt}0$ we can write $w_1w_2$ as $\underbrace{w_1x}_{x'}yz$ which stand with the claim property

2.5 Exercise 5

(a) Lets L be a regular language over alphabet $\Sigma $. and we will proof the language $L'$ define $L'=\lbrace xyz:xy^Rz \in L \rbrace $ is regular. since L is regular $\Rightarrow $ exists some DFA that accept L $M=(Q,\Sigma ,\delta ,q_0,F)$ now lets define few new DFA’s s.t:

$M_{q_0,q_k}=(Q,\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})=\lbrace w :\exists q_k,q_j \in Q | \text{ exists path s.t }q_k \rightsquigarrow q_j \rbrace $ ,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,\Sigma ,\delta ,q_k,F)$ for any $q_k\in Q $ this DFA will cover any path that end in $F$

claim 2.3

$L'=\cup _{q_i,q_j}L(M_{q_0,q_i})||L(M_{q_i,q_j})^R||L(M_{q_j,F})$

Proof ▼

\[ w=xyz \in L' \Leftrightarrow xy^Rz \in L \Leftrightarrow \exists \hat{\delta }(\hat{\delta }(\hat{\delta }(q_0,x),y^R),z) \in F_m \Leftrightarrow \]

\[ \exists M_{q_0,q_i}:\hat{\delta }(q_0,x)\in F_{ M_{q_0,q_i}} \wedge \exists L(M_{q_i,q_j})^R : y\in L(M_{q_i,q_j})^R \wedge \exists M_{q_j,F}:\hat{\delta }(q_j,z)\in F_{ M_{q_j,F}}=F_m \]

\[ \Leftrightarrow xyz\in \cup _{q_i,q_j}L(M_{q_0,q_i})||L(M_{q_i,q_j})^R||L(M_{q_j,F}) \]

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

$L=\lbrace x\in \Sigma ^* : x\in L \rbrace $ and $\overline{L}=\lbrace x\in \Sigma ^* : x\notin L \rbrace $ are regular.
$L||\overline{L}=\lbrace xy\in \Sigma ^* : x\in L \wedge y \notin L \rbrace $ and $\overline{L}||L=\lbrace xy\in \Sigma ^* : x\notin L \wedge y \in L \rbrace $ are regular.
$(L||\overline{L}) \cup (\overline{L}||L)=\lbrace xy\in \Sigma ^* : (x\in L \wedge y\notin L )\vee (x\notin L \wedge y\in L ) =(x\in L) \text{ XOR } (y\in L) \rbrace $ is regular

Exercise 6

$\text{\textbf{(a)} }\lbrace w \in \Sigma ^*: \# _0 (w) \leq 3 \rbrace $
lets express the following as regular expression

\[ \underbrace{1^*}_{I}\cup \underbrace{1^*01^*}_{II} \cup \underbrace{1^*01^*01^*}_{III}\cup \underbrace{1^*01^*01^*01^*}_{IV} \]

(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)} }\lbrace w \in \Sigma ^*:|w| \text{ mod 4}=2 \rbrace $
lets express the following as regular expression

\[ \underbrace{(0 \cup 1 )(0\cup 1) }_{(I)}\underbrace{((0\cup 1)(0\cup 1)(0\cup 1)(0\cup 1))^*}_{II} \]

(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

\[ \mathcal{L=} \{ \# 1^n \# x_1 \ldots x^n : \exists i\neq j \text{ s.t } x_i \neq x_j \} \]

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

\[ Q=\lbrace q_0,q_a,q_r \rbrace ,\Sigma =\{ 1,\# \} ,\Gamma =\{ 1,\# ,\sqcup \} \]

and define $\delta $ :

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

3.2 Exercise 2

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

\[ Q=\lbrace q_{m},q_a,q_r \rbrace ,\Sigma =\Sigma ,\Gamma =\Sigma \cup \{ \{ q\in Q\} ,\sqcup \} ,q_0=q_{m} \]

\[ \delta (q,(\sigma _1,\sigma _2))= \begin{cases} (q_m,(\sigma _1,\delta (q_0,\sigma _1),(R,L)) & \quad \text{if } \sigma _1 \in \Sigma \wedge \sigma _2=\sqcup \\ (q_m,(\sigma _1,\delta (\sigma _1,\sigma _2)),(R,L)) & \quad \text{if } \sigma _1 \in \Sigma \wedge \sigma _2=q\in Q/F \\ (q_a,(\sigma _1,\sigma _2),(R,L)) & \quad \text{if } \sigma _1= \sqcup \wedge \sigma _2=q\in F \\ (q_r,(\sigma _1,\sigma _2),(R,L)) & \quad \text{if } \sigma _1= \sqcup \wedge \sigma _2=q\notin F \\ \end{cases} \]

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

\[ Q=\lbrace q_{m2},q_a,q_r \rbrace ,\Sigma =\Sigma ,\Gamma =\Sigma \cup \{ q\in Q\} ,q_0=q_{m2} \]

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

\[ \delta (q,(\sigma _1,\sigma _2))= \begin{cases} (q_m,(\hat{\sigma },\hat{q}),(\hat{D},L)) & \quad \text{if } \sigma _1 \in \Sigma \wedge \sigma _2=\sqcup \\ (q_m,(\hat{\sigma },\hat{q}),(\hat{D},L)) & \quad \text{if } \sigma _1 \in \Sigma \wedge \sigma _2=q\in Q \\ (q_a,(\sigma _1,q_a),(R,L)) & \quad \text{if } \sigma _2=q_a \wedge \forall \sigma _1 \\ (q_r,(\sigma _1,q_r),(R,L)) & \quad \text{if }\sigma _2=q_r \wedge \forall \sigma _1 \\ \end{cases} \]

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

Exercise 3

Proposition 1

Disprove $\mathcal{RE}$ is not closed under complement.

For $L,\overline{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, $\forall L \in \mathcal{RE}, \overline{L} \in \mathcal{RE}\Rightarrow $ we get that $\mathcal{RE}=\mathcal{R} \Rightarrow \clubsuit $

Proposition 2

$co\mathcal{RE}$ is closed under intersection.

By detention $L \in co\mathcal{RE}$ if $\overline{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 :

\[ L_1,L_2\in \mathcal{RE} \Rightarrow L_1\cup L_2\in \mathcal{RE}\Rightarrow \overline{ L_1\cup L_2}\in co\mathcal{RE}\Rightarrow \overline{ L_1} \cap \overline{ L_2}\in co\mathcal{RE} \]

Proposition 3

$\mathcal{R}$ is closed under Kleene star.

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^*$ that accept $L^*$ for input x .

if $x=\epsilon $ 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 $\forall w\in \{ x_i \} $, if for some $x_i$ L accept all $w\in \{ x_i\} $ Accept.

else Reject.

Proposition 4

$\mathcal{RE}$ is closed under Prefix, but $\mathcal{R}$ is not closed under Prefix,

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

\[ f_{prefix}= w:=\{ \sigma _1\dots \sigma _k \} \forall k: 0{\lt}k{\lt}|w| \text{ for any }f_{\mathcal{L}}=w \]

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/R}$. now lets construct new $\hat{L}$ consisting of strings from the encode of $M_F$ and $\# $ i.e $M_F\# $ now I claim that $\hat{L}$ Accept only when its see $\# $ ,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 \clubsuit $

3.4 Exercise 4

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

\[ \text{Size}(O(n)) = \left\lbrace \mathcal{L} :\exists \mathcal{C}:=\{ C_n\} _{n\in N}\text{ s.t } \mathcal{L(C)=L} \wedge |C_n|\in O(n) \forall n\in N \right\rbrace \]

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_U}$

\[ \mathcal{L_U} := \{ 1^n | \text{ The Turing machine encode to n halts on $\epsilon $.}\} \]

Hence its immediate from Rice’s Theorem, or the fact that $ H_{TM\epsilon }$ $\leq _m \mathcal{L_U}$ that $\mathcal{L_U} \notin \mathcal{R}$ and $\mathcal{L_U}\in \text{Size}(O(n)) $

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

\[ \mathcal{L} =\{ 1^{2^n} : n\geq 0 \} \]

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

Prove: If $\mathcal{L}_1 \leq _m \mathcal{L}_2$ and $\mathcal{L}_2 \leq _m \mathcal{L}_3, $ then $ \mathcal{L}_1 \leq _m \mathcal{L}_3. $
Define $f_{1\rightarrow 2},f_{2\rightarrow 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\Leftrightarrow f_{1\rightarrow 2}(w)\in \mathcal{L}_2 \Leftrightarrow f_{2\rightarrow 3}(f_{1\rightarrow 2}(w))\in \mathcal{L}_3 \]
Disprove: If $\mathcal{L}_1 \leq _m \mathcal{L}_2$ and $\mathcal{L}_2 \leq _m \mathcal{L}_1, $ then $ \mathcal{L}_1 = \mathcal{L}_2.$
for $H_{TM},A_{TM}$ we know that $H_{TM}\leq _m A_{TM}$ and $A_{TM}\leq _m H_{TM}$ but $A_{TM}\neq H_{TM}\Rightarrow \clubsuit $
Disprove: If $\mathcal{L}_1 \subseteq \mathcal{L}_2$ then $ \mathcal{L}_1 \leq _m \mathcal{L}_2.$
Lets look at $\mathcal{L} = \Sigma ^*$,$\mathcal{L} \in \mathcal{R}$ since any other $\mathcal{L}'\subseteq \mathcal{L}$. if we assume that $\forall \mathcal{L}' \leq _m \mathcal{L}$ its will lead to $\forall \mathcal{L} ' \in \mathcal{RE} \Rightarrow \clubsuit $
Disprove: For every $\mathcal{L}_1,\mathcal{L}_2$, then $\mathcal{L}_1 \leq _m \mathcal{L}_2$ or $\mathcal{L}_2 \leq _m \mathcal{L}_1$
Lets look at $A_{TM},\overline{A_{TM}}$. If we assume $\overline{A_{TM}} \leq _m A_{TM}$ Since $\overline{A_{TM}}\notin \mathcal{RE}$ its will lead to $A_{TM}\in \mathcal{R}\Rightarrow \clubsuit $,
and if $A_{TM} \leq _m \overline{A_{TM}} $ Since $A_{TM}\notin \text{co-}\mathcal{RE}\Rightarrow \overline{A_{TM}}\in \mathcal{R}\Rightarrow \clubsuit $
Prove: If $\mathcal{L}$ is regular, then $\mathcal{L} \leq _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{cases} \langle M,w\rangle & \quad \text{if } w\in M \\ \langle M_{loop},w\rangle & \quad \text{if } w\notin M\\ \end{cases} \]

Which imply $\mathcal{L} \leq _m HALT$

3.6 Exercise 6

(a) $\mathcal{L} = \{ \langle M\rangle : M $ is a TM and $|L(M)| {\gt} 10\} \in \mathcal{RE/R}$

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

---

$A_{10}$ on input $\langle M\rangle $ $\langle M\rangle $ is a valid encode of TM
else Reject $k$ $\leftarrow $ 1 $k {\lt} \infty $ counter $\leftarrow $ 0 $i$ $\leftarrow $ 1 to $k$ simulate $M$ on $w_i$ for $k$ steps$w_i$ generated from $\Sigma $ of $M$ $M$ acceptcounter + 1 counter ${\gt}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$\leq _m \mathcal{L}$. now lets define $\mathcal{M}$

---

$\mathcal{M}$ on input $\langle M,\hat{w}\rangle $ . $\langle M,\hat{w}\rangle $ 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 $\langle M,\hat{w}\rangle \in H_{TM} \Rightarrow M(\hat{w})$ halt $\Rightarrow \mathcal{M}$ accept any input $ \Rightarrow |L(\mathcal{M})|{\gt}10\Rightarrow \mathcal{M}\in \mathcal{L} $

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

\[ f(\langle M,w\rangle )=\begin{cases} \langle \mathcal{M} \rangle & \quad \text{if }\langle M,w\rangle \text{ is valid input of TM and word} \\ \langle \mathcal{M}_{favourite} \rangle & \quad \text{otherwise } \end{cases} \]

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

\[ \textbf{(B) }\mathcal{L} = \{ M : \langle M\rangle \text{ is a TM that accepts 1 but does not accept 0}\} \in \overline{\mathcal{RE}\cup \text{co-} \mathcal{RE}} \]

Lets look at

\[ \mathcal{L}_{1\wedge \neg 2}=\{ \langle M_1,w_1,M_2,w_2\rangle | w_1 \in L(M_1) \wedge w_2 \notin L(M_2)\} \]

since we know that $\mathcal{L}_{1\wedge \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 \neg 2}$ that work as follow:

None

$\mathcal{M}_{1\wedge \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\neq 0\wedge w\neq 1$ Accept
I claim that exists maping function $f$ from $\mathcal{L}_{1\wedge \neg 2}$ to $\mathcal{L}$ s.t:

\[ f(\langle M_1,w_1,M_2,w_2\rangle )=\begin{cases} \langle \mathcal{M}_{1\wedge \neg 2} \rangle & \quad \text{if }\langle M_1,w_1,M_2,w_2\rangle \text{ is valid input of 2 TMs and 2 words} \\ \langle \mathcal{M}_{0} \rangle & \quad \text{otherwise } \end{cases} \]

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

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

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

(c) $\mathcal{L} = \{ \langle M_1,M_2\rangle : M_1,M_2 $ are TMs and $\mathcal{L}(M_1)\cap \mathcal{L}(M_2)=\emptyset \} \in \text{co-} \mathcal{RE/R}$

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

None

$\mathcal{A}$ on input $\langle M_1,M_2\rangle $ $k$ $\leftarrow $ 1 $k {\lt} \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)\neq \emptyset $, $\mathcal{L} \in \text{co-} \mathcal{RE}$.
Now lets proof $\mathcal{L}\notin \mathcal{R}$ using reduction from $E_{TM}\leq _m \mathcal{L}$. and its will be sufficient to see that $\overline{E_{TM}}\leq _m \overline{\mathcal{L}}$ now lets define ND-TM $\mathcal{M}_{E}$

None

$\mathcal{M}_{E}$ on input $\langle \hat{M}\rangle $ . Guess $w$ from $\Sigma ^*$ Simulate non-deterministic $M$ on $w$
And let define $f$ s.t:

\[ f(\langle M\rangle )=\begin{cases} \langle \mathcal{M}_{E},\mathcal{M}_{ACC} \rangle & \quad \text{if }\langle M\rangle \text{ is valid input } \\ \langle \mathcal{M}_{E},\mathcal{M}_{\emptyset } \rangle & \quad \text{otherwise } \end{cases} \]

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

If $\langle M\rangle \in \overline{ E_{TM}}\Rightarrow \mathcal{L}(M)\neq \emptyset \Rightarrow \mathcal{L(M}_{E})\cap \mathcal{L(M}_{ACC})\neq \emptyset \Rightarrow \langle \mathcal{M}_{E},\mathcal{M}_{ACC} \rangle \in \overline{\mathcal{L}}$

If $\langle M\rangle \notin \overline{ E_{TM}}\Rightarrow \mathcal{L}(M)= \emptyset \Rightarrow \mathcal{L(M}_{E})\cap \mathcal{L(M}_{ACC})=\emptyset \Rightarrow \langle \mathcal{M}_{E},\mathcal{M}_{ACC} \rangle \notin \overline{\mathcal{L}}$.

(d) $\mathcal{L} = \{ \langle M_1,M_2\rangle : 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=\{ \langle M_1,M_2\rangle :\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\leq _m \mathcal{L}$. Now lets construct a TM $\mathcal{M}_{EQ}$ that work as follow:

None

$\mathcal{M}_{EQ}$ on input $\langle M_1,M_2\rangle $ . Run $M_\mathcal {L}\langle M_1,M_2\rangle $we assume that exist some TM $M_\mathcal {L}$ that halt $M_\mathcal {L}$ reject Reject $M_\mathcal {L}$ accept simulate $M_\mathcal {L}\langle M_2,M_1\rangle $ Answer like $M_\mathcal {L}\langle M_2,M_1\rangle $
We can see that $\mathcal{M}_{EQ}$ decides $EQ$, since $\mathcal{M}_{EQ}$ accept $\Leftrightarrow \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_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 $\clubsuit $

4 Section 4

4.1 Exercise 1

(a)

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

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

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

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

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_{\textbf{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.

None

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

(b)

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

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

$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: \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}$ .

None

$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 $\emptyset \in C$. then

\[ \mathcal{L_C} =\{ \langle M \rangle : 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'}\in \mathcal{RE} $ such that $\mathcal{L'}\notin \mathcal{C}$. Let $M_{\mathcal{L'}}$ denote TM that accept $\mathcal{L'}$

5 Section 5

5.1 Exercise 1

Assuming $P\ne NP$

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_iv_j \in A_i \Leftrightarrow v_iv_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$
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 $\langle G,v_i,v_j \rangle $ for any $i,j$ .now by choose any triplet from $\{ 1\dots n\} ^3$ and check if STCON$\langle G,v_i,v_j \rangle $ return 0 for any $i,j\in \{ i,j,l\} $ in total we run $n \choose 2 $ times STCON save result on the tape size $n \choose 2 $ and check the nation for any triplet in total $n \choose 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 _P3-$MDS.
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\neq \emptyset $
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 \Leftrightarrow $ for any $e=v_iv_j$ exists $x\in A_i,A_J$ $\Leftrightarrow $ $A_i\cap A_j$ for any $i\ne j$.
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.
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,\neg x_i $ does Not appear together $\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.
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.
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'$ by adding set of additional $|V'|=|V|$ isolated vertexes. now define

\[ f(\langle G=(V,E) ,k \rangle )=\langle G'=(V+V',E) ,k+|V| \rangle \]

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

5.2 Exercise 2

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$
None
$f$ on input $w$ . Decide $w\in L_1$ If $w\in L_1$ Return any $w'\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 \emptyset $ and 3$^{\text{nd}}$ since $L_2\ne \Sigma ^*$. All the following can done in poly-time hence $f$ poly-time computable reduction function from $L_1\le _P L_2$
For every nontrivial $L_1,L_2\in NP, L_1\le _P L_2$
Equivalent to an Open Problem

claim

$P=NP$ $ \Leftrightarrow $ 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 _pL_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=\emptyset \Rightarrow NP\subseteq P\Rightarrow P=NP$
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)=\langle \mathcal{M} ,w \rangle $ 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 \Leftrightarrow \langle \mathcal{M} ,w \rangle \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
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 _PSAT$ decide SAT. Let look at d-TM $\mathcal{M}'$.
None
$\mathcal{M}'$ on input $w$ . Computes $f(w)$ Simulate $\mathcal{M}_{SAT}(f(w))$ and Answer like $\mathcal{M}_{SAT}$
$w\in L \Leftrightarrow \mathcal{M}_{SAT}$ accept $f(w) \Leftrightarrow 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}'(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'}$ that given a formula $\psi =\alpha (x_1,x_2\dots x_N)$ work such that:

None

$\mathcal{M}'$ on input $\psi $ . check if $\psi $ is valid 3CNF formula, otherwise Reject Simulate $\mathcal{M}_{3CNF}\langle \psi \rangle $ and Reject if $\mathcal{M}_{3CNF}\langle \psi \rangle $ Reject $\alpha (x_1,x_2\dots x_N)\gets \psi $$\alpha $ represent the logic relation w.r.t $\psi $ $ y_j\gets 0 \quad \quad 1\le j \le N$ $i\gets 1$ $i \le N$ Simulate $\mathcal{M}_{3CNF}\langle \alpha (y_1,y_2\dots y_{i-1}, T, x_{i+1}\dots x_N)\rangle $ $\mathcal{M}_{3CNF}$ Accept$y_i \gets T$ $\mathcal{M}_{3CNF}$ reject $y_i\gets F$ $\alpha (x_i)\gets y_i$ output $y_i\dots y_N$
If $\psi $ does not have an boolean satisfy assignment then $\mathcal{M}'$ indicate that at step 2. The correctness of $\mathcal{M}'$ 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}'$ 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 \Sigma ^*$ such that $n_0\le x , |f(x)|\le |x|-1$. Assuming $P\ne NP$

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,\overline{b}\notin B$. Consider $f$ s.t

\[ f(w)=\begin{cases} b & \quad \text{if } w \in A \\ \overline{b} & \quad \text{if } w \notin A \\ \end{cases} \]

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

\[ x\in \Sigma ^* \text{ s.t }n_0\le |x| \qquad |f(x)|\le \max \{ |\overline{b}|,|b|\} \le n_0-1 \le |x|-1 \]
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|{\lt} n_0$. We can encode them all correct answers to an algorithm $\mathcal{A}$. For given $x\in \Sigma ^*$ if $|x|{\lt} n_0$ then its encoded already to $\mathcal{A}$. Since $f(x){\lt}|x|$, when $|x|\ge n_0$ we can apply finite time of $ff\dots (x)$ until we achieve some $|w|{\lt}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:

\[ EXACT3SAT=\{ \varphi \in 3SAT:\text{every clause of $\varphi $ 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=\emptyset $ 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{align*} f(\emptyset )& =(x\vee y\vee z)\wedge (x\vee y\vee \neg z)\wedge (x\vee \neg y\vee z)\wedge (x\vee \neg y\vee \neg z)\wedge \\ & (\neg x\vee y\vee z)\wedge (\neg x\vee y\vee \neg z)\wedge (\neg x\vee \neg y\vee z)\wedge (\neg x\vee \neg y\vee \neg z) \end{align*}

$\emptyset \equiv f(\emptyset )$

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

\[ f((x))=(x\vee y \vee z)\wedge (x\vee \neg y \vee z)\wedge (x\vee y \vee \neg z)\wedge (x\vee \neg y \vee \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 \neg z) \]

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

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

Hence let $f'(\psi )=f'(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$
\[ L_2=\{ \langle M,1^n \rangle :\text{M is a TM and there exists a string that M accepts in n steps}\} \]

Proof ▼

First consider some $w=\langle M,1^n \rangle $ we can verify that $w\in L_2$, by simulate M on any input size $n$ that is ⁴ $n^{|\Sigma ^*|}\in \mathcal{O}(n)$, and in total $\mathcal{O}(n^{|\Sigma ^*|} |M|^3n \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 \Leftrightarrow \exists c \quad \text{s.t } (x,c)\in V_L \Leftrightarrow f(x)=\langle V_L,1^{p(|x|)}\rangle \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 _PPCON \]

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.
If $\langle G,P \rangle \in PCON \Rightarrow $ exist some $(u,v)\in P$ s.t $u \leadsto v$ and $v \leadsto u \Rightarrow $ exist cycle $C \subseteq G$ such that $u,v\neg ,u,\neg v\in C$ and $v \leadsto \neg v \leadsto v\in G \Rightarrow $ any $x_1\dots x_v \dots x_n$ that satisfies $\varphi $ following that $x_1\dots \neg x_v \dots x_n $ satisfies $\varphi $ as well $\Rightarrow v\equiv \neg v $ contradiction.
⁵ If $\langle G,P \rangle \notin PCON$ then $t$ is well defined, since if $ v \leadsto \neg u ,v \leadsto u $ then by $f$ definition $v \leadsto u\leadsto \neg v$. and when we looking at closure size 1 $(u)$ then both $u,\neg u$ reachable as well. Hence if $\langle G,P \rangle \notin PCON$ then $P \not\subseteq G \Rightarrow $ for any $u,v$ exist $e$ s.t $e\in (V\times V) ,e \notin E$ $t(v)=1$ then $v \not\leadsto \neg v$ for any $v\in G$. then $\forall \ell _1 \in \varphi $ we get that $t(\ell )\bigoplus t(\neg \ell )=1$. and we can consider it as

\[ t=\left(t(\ell _1)\bigoplus t(\neg \ell _1)\right)\vee \left(t(\ell _2)\bigoplus t(\neg \ell _2)\right) \dots \]

And its immediate that t satisfies $\varphi $

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$

None

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