%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the "author" and "collaborators" fields as
% appropriate. Write your solutions where indicated.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi


\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother

\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}

\begin{document}


\begin{center}
{\Large CS 535: Complexity Theory, Fall 2023}

\bigskip

{\Large Homework 2}

\smallskip

Due: 11:59PM, Tuesday, September 12, 2023.

\end{center}

\ifnum\inclsolns=1
	\makeatletter
	\noindent Name: \@author \\
	Collaborators: \@collaborators
	\makeatother
\else
\fi

\paragraph{Reminder.}
Homework must be typeset with \LaTeX\ preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions {\em by
	yourself without assistance}. You must also identify your
collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the
Web or students not enrolled in the class is strictly forbidden.

\bigskip


\begin{problem}[$\coNP$]
	Recall that the complexity class $\coNP$ consists of languages $L$ such that $\overline{L} \in \NP$.
	\begin{enumerate}[(a)]
		\item Show that a language $L$ is $\NP$-complete if and only if $\overline{L}$ is $\coNP$-complete. Recall that completeness for both classes is defined with respect to polynomial-time (Karp) reductions. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Recall that the set difference operation on two languages $A, B$ is defined by $A \setminus B = \{x \mid x \in A, x \notin B\}$. Is $\NP$ closed under the set difference operation? That is, is it the case that for every $A, B \in \NP$, we have $A \setminus B \in \NP$? Justify your answer. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Define the language
		\[\mathsf{FACTOR} = \{\langle m, k \rangle \mid m \text{ has a prime factor } p \text{ such that } p \le k\}.\]
		Here, the numbers $m$ and $k$ are written in binary. Show that if $\mathsf{FACTOR}$ is $\NP$-complete, then $\NP = \coNP$.
		
		You can use without proof that there is a polynomial time algorithm for testing whether a number $p$ (written in binary) is prime. (6 points)
	
	\begin{solution}
		Your solution here.
	\end{solution}
		
		
		\item Find the first error in the following ``proof'' that $\NP = \coNP$, and explain why it is an error:
		Let $M$ be a nondeterministic polynomial-time algorithm deciding
				\[\mathprob{FSAT} = \{\varphi \text{ a Boolean formula } \mid \exists x \ \varphi(x) = 1\}.\]
		 We design a nondeterministic polynomial-time algorithm deciding
		\[\mathprob{TAUT} = \{\varphi \text{ a Boolean formula } \mid \forall x \ \varphi(x) = 1\}\]
		as follows. On input $\varphi$ (an instance of $\mathprob{TAUT}$), evaluate $b = M(\neg \varphi)$. If $b = 0$, output $1$, and if $b = 1$, output $0$. This runs in nondeterministic polynomial-time as long as $M$ does, and $\varphi \in \mathprob{FSAT}$ iff $\neg \varphi \notin \mathprob{TAUT}$, so it decides $\mathprob{TAUT}$. Therefore, $\mathprob{TAUT} \in \NP$. Since $\mathprob{TAUT}$ is $\coNP$-complete, it follows that $\coNP \subseteq \NP$. A similar argument shows that $\NP \subseteq \coNP$, hence $\NP = \coNP$. (2 points)
		
				\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}

\begin{problem}[Class Assignments]
	As the principal of an elementary school, one of your jobs is to determine class assignments for the $n$ students entering 2nd grade. The first grade teachers generated a list of ``disruptive friend groups,'' which are subsets $G_1, G_2, \dots, G_m \subseteq [n]$ such that the presence of any complete friend group $G_i$ in a classroom will be...problematic.
	
	Is it possible to partition the $n$ students into two classrooms such that every disruptive friend group is split between the two classes? That is, do there exist disjoint sets $S_1, S_2$ such that $S_1 \cup S_2 = [n]$ and for every friend group $G_i$, we have $G_i \not\subseteq S_1$ and $G_i \not\subseteq S_2$?
	
	Define the language $\mathsf{PC}$ (short for ``peaceful classrooms'') such that an instance $\langle n, G_1, \dots, G_m\rangle \in \mathsf{PC}$ if and only if there exists an appropriate partition of the $n$ students described above. Show that the language $\mathsf{PC}$ is $\NP$-complete via a poly-time reduction from $\mathsf{3SAT}$. (8 points)
\end{problem}

\begin{solution}
	Your solution here.
\end{solution}

\end{document}






