Problem 1: \\
Prove that the following language is not Turing-recognizable: \[L = \{ \langle G_1 \rangle, \langle G_2 \rangle, \langle G_3 \rangle \mid G_1, G_2, \text{ and } G_3 \text { are CFG's and } L(G_1)=L(G_2)=L(G_3) \}.\]Hint: You can assume that the following language is undecidable (see page 200 of the textbook): \[EQ_{CFG} = \{ \langle G, H \rangle \mid G \text{ and } H \text{ are CFGs and } L(G)=L(H) \}\]

Problem 2: \\
Prove that for any language $A$, $A$ is Turing recognizable if and only if $A\leq_m A_{TM}$.

Problem 3: \\
Boolean variables can take on values of TRUE or FALSE.
Boolean operators are $\wedge$ (and), $\vee$ (or) and $\neg$ (not).
A Boolean formula is an expression with Boolean variables and operators
A Boolean formula is satisfiable if some assignment of 0s and 1s to the variables makes the formula evaluate to TRUE. For example, the formula $(\neg x \vee y) \wedge (x \vee \neg z)$ is satisfiable by several assignments including $x=FALSE$, $y=TRUE$, $z=FALSE$. 

In the Boolean Satisfiability problem (SAT), given a Boolean formula $\phi$, we aim to decide whether $\phi$ has any satisfying assignments. That is, given the  encoding $\langle \phi \rangle$ of the Boolean formula $\phi$ we aim to decide whether $\langle \phi \rangle$ is a member of the language 
$$
SAT=\{\langle \phi \rangle |\phi\textrm{ is a satisfiable Boolean formula}\}.
$$
As we will see in class, $SAT$ is a very \emph{HARD} problem. However, we can study variations of the problem that are considerably \emph{easier}.

A \emph{clause} is a type of Boolean formula in which literals (Boolean variables or their negation) are connected by only "or" operators. For example $(x_1 \vee x_2 \vee \neg x_1)$ is a clause. We say that a Boolean formula is in Conjunctive Normal Form (CNF) or clausal normal form if it is a conjunction (and) of one or more clauses. For example $(x_1 \vee x_2 \vee \neg x_1)\wedge (x_1 \vee x_3 \vee \neg x_2)\wedge x_1 \wedge (x_2 \vee \neg x_1)$ is a CNF Boolean formula.

We will consider CNF Boolean Formulas such that each variable appears at most twice (including the times that it appears as negated). For example, in $(x_1 \vee x_2 \vee \neg x_1)\wedge (x_3 \vee x_3 \vee \neg x_2)\wedge x_4 \wedge (x_6 \vee \neg x_7)$ each variable occurs at most twice, while in $(x_1 \vee x_2 \vee \neg x_1)\wedge (x_1 \vee x_3 \vee \neg x_2)\wedge x_1 \wedge (x_2 \vee \neg x_1)$ that is not the case ($x_1$ appears 5 times).

Consider  the language. 
$
2RCNFSAT= \{\langle \phi \rangle|\phi$ is a satisfiable CNF Boolean formula in which each variable occurs at most twice $\}$.


Prove that $2RCNFSAT\in TIME(n^k)$, where $n$ is the size of the encoding of a Boolean formula and $k$ is some constant value independent of $n$. That is, provide an algorithm that decides whether an input $\langle \phi \rangle$ is a member of 2RCNFSAT in polynomial time with respect to the size of the input. Here you can assume that the size of the input is the number of literals in $\phi$ (i.e., the sum of occurrences of variables in $\phi$). For example, if $\phi = (x_1 \vee x_2 \vee \neg x_1)\wedge (x_1 \vee x_3 \vee \neg x_2)\wedge x_1 \wedge (x_2 \vee \neg x_1)$, $|\phi|=n=9$.