Homework 2

This homework covers the material from lectures 5 to 11.

Due date: October 11th, 10pm Waterloo time.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Problem 1 - Basic Relations Between Complexity Classes (20 points)

1. Prove that $\texttt{P} \subseteq \texttt{NP} \cap \texttt{coNP}$.

2. Suppose that $L_1, L_2 \in \texttt{NP}$. Is it true that $L_1 \cup L_2 \in \texttt{NP}$? What about $L_1 \cap L_2$? Justify your answers with a proof.

Problem 2 - NP Completeness (20 points)

Let $\Phi := C_1 \wedge C_2 \wedge \cdots \wedge C_m$ be a 3CNF formula. An $\neq$-assignment to the variables of $\Phi$ is an assignment that satisfies $\Phi$ but for every clause $C_i$, at least one of the literals in $C_i$ is set to false.

1. Show that the negation of a $\neq$-assignment is also a $\neq$-assignment.

2. Let $\neq$-3SAT be the collection of 3CNF formulas that have a $\neq$-assignment. Show that $\neq$-3SAT is NP-complete.

Hint: Reduce from 3SAT. What happens if you replace clause $(y_1 \vee y_2 \vee y_3)$ with $(y_1 \vee y_2 \vee z) \wedge (\neg z \vee y_3 \vee b)$ for a new variable $z$ and a new variable $b$?

Problem 3 - Max-Cut (20 points)

A cut in an undirected graph $G = (V, E)$ is a partition of the vertices $V$ into disjoint sets $S$ and $V \setminus S$. The size of the cut $(S, V \setminus S)$ is the number of edges that have one endpoint in $S$ and the other in $V \setminus S$. Let $$\text{MAX-CUT} := \{ \langle G, k \rangle \mid G \text{ has a cut of size at least } k \}.$$ Show that $\text{MAX-CUT}$ is NP-complete. You may assume the result from problem 2.

Hint: Reduce from $\neq$-3SAT. Here is one possible way. Given an instance $\Phi = C_1 \wedge \cdots \wedge C_m$ of $\neq$-3SAT, construct a graph $G$ as follows: for each variable $x_i$ in $\Phi$, construct $3m$ nodes labeled $x_i$ and $3m$ nodes labeled $\overline{x_i}$. All nodes labeled $x_i$ are connected to all nodes labeled $\overline{x_i}$. For each clause $C_j = y_1 \vee y_2 \vee y_3$ in $\Phi$, add a clique of size 3 with nodes labeled $y_1$, $y_2$, and $y_3$ (do not use the same node in more than one clique). Prove that this works.

Problem 4 - Polynomial Hierarchy (20 points)

1. Show that if $\texttt{P} = \texttt{NP}$, then $\texttt{PH} = \texttt{P}$.

2. The VC-dimension is an important concept in computational learning theory. If $\mathcal{S} = \{S_1, S_2, \ldots, S_m\}$ is a collection of subsets of a finite set $U$, the VC-dimension of $\mathcal{S}$, denoted $\text{VCdim}(\mathcal{S})$, is the size of the largest subset $X \subseteq U$ such that for every $Y \subseteq X$, there exists $S_i \in \mathcal{S}$ such that $Y = S_i \cap X$. In this case, we say that $X$ is shattered by $\mathcal{S}$.

   A boolean circuit $C$ succinctly represents a collection $\mathcal{S}$ of subsets of $U$ if $S_i$ consists of all $x \in U$ such that $C(i, x) = 1$.

   Let

   $$\text{VC-DIMENSION} := \{ \langle C \rangle, k \mid C \text{ succinctly represents } \mathcal{S} \text{ such that } \text{VCdim}(\mathcal{S}) \geq k \}.$$

   Prove that $\text{VC-DIMENSION} \in \Sigma_3^p$.

Problem 5 - Circuits for Majority (20 points)

1. We can consider circuits that output strings over $\{0,1\}$ by considering a circuit with multiple output gates. Let $\texttt{add}_n : \{0,1\}^{2n} \to \{0,1\}^{n+1}$ be the function that takes two $n$-bit strings $x$ and $y$ (the bit representation of two integers) and outputs the $(n+1)$-bit string that represents the sum of $x$ and $y$ in binary. Show that we can compute $\texttt{add}_n$ by a family of circuits $\{C_n\}_{n \in \mathbb{N}}$ such that $\text{size}(C_n) = O(n)$.

2. Define the function $\texttt{majority}_n : \{0,1\}^{n} \to \{0,1\}$ as follows: $$\texttt{majority}_n(x_1, x_2, \ldots, x_n) = \begin{cases} 1 & \text{if } \sum_{i=1}^n x_i \geq \frac{n}{2} \\ 0 & \text{otherwise}. \end{cases}$$

   Show that $\texttt{majority}_n$ can be computed by a family of circuits $\{C_n\}_{n \in \mathbb{N}}$ such that $\text{size}(C_n) = O(n \log n)$.