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 $\mathtt{\text{P}}\subseteq \mathtt{\text{NP}}\cap \mathtt{\text{coNP}}$.

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

Problem 2 - NP Completeness (20 points)

Let $\mathrm{\Phi }:=C_1\wedge C_2\wedge \cdots \wedge C_m$ be a 3CNF formula. An $\ne$-assignment to the variables of $\mathrm{\Phi }$ is an assignment that satisfies $\mathrm{\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 $\ne$-assignment is also a $\ne$-assignment.

2. Let $\ne$-3SAT be the collection of 3CNF formulas that have a $\ne$-assignment. Show that $\ne$-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 (\mathrm{\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}:=\{⟨G,k⟩\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 $\ne$-3SAT. Here is one possible way. Given an instance $\mathrm{\Phi }=C_1\wedge \cdots \wedge C_m$ of $\ne$-3SAT, construct a graph $G$ as follows: for each variable $x_i$ in $\mathrm{\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 $\mathrm{\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 $\mathtt{\text{P}}=\mathtt{\text{NP}}$, then $\mathtt{\text{PH}}=\mathtt{\text{P}}$.

2. The VC-dimension is an important concept in computational learning theory. If $\mathcal{S}=\{S_1,S_2,\dots ,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}:=\{⟨C⟩,k\mid C\text{ succinctly represents }\mathcal{S}\text{ such that }\text{VCdim}(\mathcal{S})\ge k\}.$$

   Prove that $\text{VC-DIMENSION}\in {\mathrm{\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 ${\mathtt{\text{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 ${\mathtt{\text{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 ${\mathtt{\text{majority}}}_n:\{0,1{\}}^n\to \{0,1\}$ as follows: $${\mathtt{\text{majority}}}_n(x_1,x_2,\dots ,x_n)=\{\begin{array}{ll}1& \text{if }\sum _{i=1}^n{x}_i\ge \frac{n}{2}\\ 0& \text{otherwise}.\end{array}$$

   Show that ${\mathtt{\text{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)$.