\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage{graphicx, epsfig}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\polyL}{\mbox{PolyLog}}
\newcommand{\Poly}{\mbox{P}}
\newcommand{\NL}{\mbox{NL}}
\newcommand{\NP}{\mbox{NP}}
\newcommand{\IP}{\mbox{IP}}
\newcommand{\SPACE}{\mbox{SPACE}}
\newcommand{\SC}{\mbox{PolyLogSpacePolyTime}}

\head{CSG714}{Theory of Computation}{Spring 2009}{6 April 2009}{20}

\begin{center}
\Large{\bf (Optional) Problem Set 6}
\end{center}

{\bf 1. (6 points) Variants of IP} 

Let $\IP_1$ be the class obtained if we change the soundness
error of $\IP$ from $1/3$ to $0$, leaving the completeness error
unchanged.  Let $\IP_2$ be the class obtained if we change the
completeness error of $\IP$ changed from $1/3$ to $0$, leaving the
soundness error unchanged.  What are the classes $\IP_1$ and $\IP_2$;
i.e., how are they related to $\IP$ and other classes we have studied?
Justify your answers.

{\bf 2. (3 $\times$ 6 = 18 points)} For each of these statements,
indicate whether it is true, it is false, or we do not know.  In each
case, justify your answer.
\begin{itemize}
\item[{\bf (a)}] If $R$ is a regular language and $N$ is a non-regular
language, then $N - R$ is always non-regular.

\item[{\bf (b)}] If $L_1$ and $L_2$ are in $\NL$, then $L_1 - L_2$ is
in $\NL$.

\item[{\bf (c)}] For any two languages $L_1$ and $L_2$ in $\NP$, if
$L_1 \le_P L_2$, then $L_2 \le_P L_1$.
\end{itemize}

{\bf 3. (6 points) Maximum independent set} 

An independent set of a graph $G = (V, E)$ is a subset $S$ of $V$ such
that no two vertices in $S$ have an edge between them in $E$.  It is
well known that the following language is \NP-complete.
\[
\{\langle G, k\rangle: G \mbox{ has an independent set of size } k
\}
\]
Show that if $\Poly = \NP$, then a maximum independent set of any graph
can be found in polynomial time.
\end{document}