\textbf{Problem 1:} \\
Let $\phi$ be Boolean Formula in CNF, and let $ALLBUT2SAT =\{<\phi>|\ \exists \phi'$ which includes all the clauses of $\phi$ except  exactly two, and which is satisfiable $\}$. Show that  $ALLBUT2SAT$ is NP-complete.

\textbf{Problem 2:}\\
Let $A$ be a language such that $A \in$ NP.
\begin{enumerate}
    \item Let $B$ be a language such that $B \in$ NP. Prove that $AB = \{ x \cdot y \mid x \in A \text{ and } y \in B\} \in$ NP, so that NP is closed under concatenation.
    \item Prove that $A^* = \{ x_1 x_2 \dots x_n \mid n \geq 0 \text{ and } x_i \in A\} \in$
        NP, so that NP is closed under the Kleene star operation.
\end{enumerate}

\textbf{Problem 3:}\\
Given a graph $G=(V,E)$, we say that subset $V'\subseteq V$ is an ``\emph{$\alpha$-diverse $k$-clique}" in $G$ if:
\begin{itemize}
    \item $|V'|=k$,
    \item For all pairs $v_i,v_j\in V'$, $(v_i,v_j)\in E$ (i.e., $V'$ is a $k$-clique).
    \item For all pairs $v_i,v_j\in V'$, $v_i$ is connected to $\alpha$ vertices that are not connected to $v_j$ (and vice versa).
\end{itemize}

Let $\mathit{DCLIQUE} = \{\langle G,k,\alpha \rangle | G \text{ is a graph with an } \alpha-diverse\ k-clique\}$. 

Show that $\mathit{DCLIQUE}$ is NP-complete.
