\textbf{Problem 1:} \\
In the Maximal Clique Problem, given an undirected graph $G=(v,E)$ and a positive integer value $k$ we want to decide if $k$ is the \emph{exact} size of the largest clique in $G$. We can define the corresponding language as:\\

$MAXCLIQUE=\{<G,k>| k\text{is the exact size of the largest clique in }G\}$
\begin{enumerate}
    \item Modify the reduction $f(\cdot)$ seen in class from $3SAT$ to $CLIQUE$, to obtain a computable function $f^*(\cdot)$  that given as input $\phi$ returns a pair $(G,k)$ where $G$ is an undirected graph and $k$ is a non-negative integer value such that 
    \begin{itemize}
        \item if $\phi$ is not a Boolean formula in 3CNF, $G$ includes a single edge and $k=1$ 
        \item if $\phi$ is a satisfiable  Boolean formula in 3CNF with $k$ clauses then the exact size of the clique of maximum size in $G$ is $k$.
        \item if $\phi$ is  a not satisfiable  Boolean formula in 3CNF with $k$ clauses then the exact size of the clique of maximum size in $G$ is $k-1$.
    \end{itemize}
    \item Argue that $MAXCLIQUE$ is NP-hard.
    \item Argue that $MAXCLIQUE$ is coNP-hard.
    \item Argue that  $MAXCLIQUE\in NP \implies HAMPATH^c \in NP$
\end{enumerate}

\textbf{Problem 2:} \\
Prove that  $MAXCLIQUE\in PSPACE$.

\textbf{Problem 3:} \\
Please review with attention the definition of the TQBF language as given in the textbook on pages 338-341. Please review the proof of this language being a member of $PSPACE$ and $PSPACE$-hard.

Given a Quantified Boolean formula $\phi = Q_1x_1,Q_2x_2,\ldots Q_mx_m[\psi]$ such that $\psi$ is a Boolean formula with $m$ variables, we say that $\phi$ is a Quantified CNF Boolean formula if $\psi$ is a Boolean formula in CNF format.

The language $TQBF-CNF=\{<\phi>| \phi $ is a true fully quantified CNF Boolean formula$\}$ is also $PSPACE$-complete. 

Similarly, given a Quantified Boolean formula $phi = Q_1x_1,Q_2x_2,\ldots Q_mx_m[\psi]$ such that $\psi$ is a Boolean formula with $m$ variables, we say that $\phi$ is a Quantified 3CNF Boolean formula if $\psi$ is a Boolean formula in 3CNF format.

Consider now the language $TQBF-3CNF=\{<\phi>| \phi$ is a true fully quantified 3-CNF Boolean formula$\}$.

\begin{enumerate}
    \item Prove $TQBF-3CNF\in PSPACE$.
    \item Prove $TQBF-3CNF$ is $PSPACE$-hard.
\end{enumerate}

\noindent\emph{Hint:} Read with lots of care the results for TQBF. This should give you all the needed inspiration. For the proof of hardness, I would \emph{strongly} suggest proving $TQBF-CNF\leq_p TQBF-3CNF$. Perhaps we have seen something similar before....careful how you manage (or quantify) the new variables. 