Problem 1: \\
A language $A$ is said to be $P$-complete if $A\in P$ and if  $\forall L\in P, L\leq_p A$. 
Which one of the following statements is the most correct?
\begin{itemize}
    \item No regular language is $P$-complete.
    \item Some regular languages are $P$-complete but not all of them.
    \item All regular languages are $P$-complete.
    \item There exists a regular language which is $P$-complete iff $P=NP$.
\end{itemize}

Choose a statement you believe to be correct and provide complete proof of why is that the case. 

Problem 2: \\
Given a Boolean formula $\phi$, we say that an assignment of its Boolean variables is a \emph{satisfactory assignment} if $\phi$ evaluates to TRUE using the truth values for its variable given in the assignment.

Further, we say that two assignments of \emph{truth value} to its Boolean variable are \emph{distinct} if there is at least a variable which is assigned value TRUE in one assignment and value FALSE in the other. 

Let $QUADRUPLELESAT=\{<\phi>|\phi \textrm{ is a Boolean formula in CNF and it}$ has at least four distinct satisfying assignments$\}$. 

Show that $QUADRUPLESAT$ is $NP-complete$. Here is an outline of how to do so:
\begin{enumerate}
    \item Propose a Deterministic Verifier requiring worst case polynomial time for $QUADRUPLESAT$. Given the encoding of a Boolean formula $\langle \phi \rangle$ we say that its  \emph{size} is the number of literals in $\phi$ (i.e., the sum of occurrences of variables in $\phi$).
    \begin{enumerate}
        \item Provide a description of a deterministic polynomial-time verifier $V$ for $QUADRUPLESAT$. What is the certificate $c$ used?
        \item Prove the \emph{correctness} of your verifier: Two directions:
        \begin{itemize}
            \item  $<\phi>\in QUADRUPLESAT \implies \exists c$ s.t. the verifies accepts $<\phi>$ using $c$.
            \item $<\phi>\notin QUADRUPLESAT \implies \nexists c$ s.t. the verifies  accepts $<\phi>$ using $c$.
        \end{itemize}
        \item Prove that the proposed verifier required worst case polynomial time with respect to the size of the input and of the certificate.
    \end{enumerate}
    \item Provide a description of a nondeterministic polynomial-time decider $N$ for for $QUADRUPLESAT$.
    \begin{enumerate}
    \item Prove the \emph{correctness} of your decider $N$ that is $L(N)=QUADRUPLESAT$.
    \item Prove that your decider requires worst case non-deterministic polynomial time with respect to the size of the input.
    \end{enumerate}
    \item Describe a deterministic algorithm that given a string $w$ computes $f(w)$ such that $f(w)$ is the encoding of a Boolean formula $\phi''\in QUADRUPLESAT$ if and only if $w$ is the encoding of a \emph{satisfiable } Boolean formula $\phi'$. 
    Given a Boolean formula you can assume that its encoding can be produced (i.e., written) in time \emph{linear with respect to its size}.
    \begin{itemize}
        \item Argue the correctness of your algorithm, that is that it computes $f(\cdot)$ s.t. $w$ is the encoding of a \emph{satisfiable } Boolean formula $\iff f(w)\in QUADRUPLESAT$.
        \item Prove that your proposed algorithm runs in worst case polynomial time with respect to the size of the input (i.e., $|w|$)
    \end{itemize}
\end{enumerate}

Problem 3: \\
Given a graph $G=(V,E)$, a clique of size $k$ is a subset $V'\subseteq V$ such that (i) $|V'|=k$, and (ii) each vertex in $V'$ is connected to all other vertices in $V'$ by an edge in $E$. We say that two cliques $V'$ and $V''$ are distinct if they differ in at least one vertex 

Let $\mathit{TRIPLE-CLIQUE} = \{\langle G,k \rangle | G \text{ is a graph with at least three distinct}\ k-\text{cliques}\}$. 

\begin{enumerate}
    \item Show that $\mathit{TRIPLE-CLIQUE}\in NP$. You can either show a deterministic verifier for $\mathit{TRIPLE-CLIQUE}$ or a non-deterministic decider. You should provide a proof of correctness and of polynomial running time (as outlined in Problem 2).
    \item Given a graph $G=(V,E)$, it is possible construct a string  encoding of $G$ of size $O(|E|)$. Argue that $CLIQUE\leq_p TRIPLECLIQUE$
\end{enumerate}