Complexity Classes

PDF of Prof. Santosh’s handwritten notes is here.

In the previous classes, we derived the following relations:

$NTIME(t(n)) \subseteq TIME(c^{t(n)})$

$NSPACE(s(n)) \subseteq DSPACE(s(n)^2)$

Complexity Class P

$P = \{L : \exists \text{ TM that accepts L in polynomial time} \}$

$P = \bigcup_{k} TIME(n^k)$

Examples:

• $SHORTEST-PATH = \{ (G = (V,E), D, d_{i,j} \ge 0) : \exists \text{ s-t path of length} \le D \}$
$SHORTEST-PATH \in P$ since Dijkstra’s algorithm solves this problem in polynomial time.
• $2-SAT \in P$ as it reduces to finding strongly connected components in a graph which can be done in polynomial time.

There exist decidable languages not in $P$.

Complexity Class NP

$NP = \{L : \exists \text{ NTM that accepts L in polynomial time} \}$

We say that a NTM accepts a language in polynomial time if $\forall x \in L$ there exists an accepting path for x of length at most $|x|^k$.

$NP = \cup_{k} NTIME(n^k)$

Examples:

• $SAT = \{ F : \exists x \text{ s.t.} F(x) = 1 \}$
$SAT \in NP$ since it is possible to guess an assignment and verify if the formula is satisfied in polynomial time.
• $CLIQUE = \{ (G = (V,E), k) : \text{ G contains a clique of size k} \}$
$CLIQUE \in NP$ since it is possible to guess a subset of vertices of size $k$ and verify if it forms a clique in polynomial time.

$L \in NP$ means $\exists$ NTM s.t. $\forall x \in L, \exists$ an accepting path for $x$ of length $\le n^k$. We could interpret the accepting path as a polynomial-sized ‘proof’ that $x \in L$. So, we could also define $NP$ as the class of languages for which membership can be verified (there exists a polynomial sized certificate) by a polynomial time TM.

Does P = NP?

Clearly, $P \subseteq NP$

We don’t know if $P = NP$.

We know the following relations:

$P \subseteq NP \subseteq PSPACE \subseteq EXP$

From the Time hierarchy theorem, we also know $P \subsetneq EXP$.

Complexity Class Co-NP

Co-NP is the class of languages that are complements of languages in NP.

Examples:

• $\overline{SAT} = \{F : F \notin SAT \text{ i.e. F has no satisfying assignment} \}$
• $\overline{CLIQUE} = \{ (G = (V,E), k) : \text{ G doesn't contain a clique of size k} \}$

$Co-NP = \{ L | \exists \text{ NTM that accepts on every path in polynomial time} \}$

Unlike $NP$, it is unclear how to verify quickly that $x \in L$ for languages in $Co-NP$. For example, it is not clear if a polynomial-sized certificate exists to show that a formula $F$ is unsatisfiable, i.e. $F \in \overline{SAT}$.

Polynomial Hierarchy

In a similar manner to Co-NP, it is possible to define an entire hierarchy of complexity classes by alternating $\exists$ and $\forall$ quantifiers. First consider the following hierarchy of languanges based on $SAT$.

$SAT = \{ F : \exists x F(x) = 1 \}$ $\in NP$

$\overline{SAT} = \{ F : \forall x F(x) = 0 \}$ $\in Co-NP$

$\Sigma_2 SAT = \{ F : \exists x \forall y F(x,y) = 1 \}$ $\in \Sigma_2$

$\Pi_2 SAT = \{ F : \forall x \exists y F(x,y) = 0 \}$ $\in \Pi_2$

$\Sigma_3 SAT = \{ F : \exists x \forall y \exists z F(x,y,z) = 1 \}$ $\in \Sigma_3$

$\vdots$

$\Sigma_i SAT = \{ F : \exists x_1 \forall x_2 \exists x_3 \dots x_i F(x_1,x_2,x_3,\dots,x_i) = 1 \}$ ($i$ alternating quantifiers)

$\vdots$

To capture the notion of alternating quantifiers, we will define Alternating Turing Machines.

Alternating Turing Machines are NTMs except that every node is one of two types:

• $\exists$ type: Accepts if some path from the node accepts
• $\forall$ type: Accepts if all paths from the node accept

$\Sigma_i$TM is an ATM with $i$ alternations starting with $\exists$.

$\Pi_i$TM is an ATM with $i$ alternations starting with $\forall$.

Using the above ATMs, we could define:

$\Sigma_i TIME(f(n)) = \{ L : \exists$ $\Sigma_i \text{TM that decides L in O(f(n)) time} \}$

$\Pi_i TIME(f(n)) = \{ L : \exists$ $\Pi_i \text{TM that decides L in O(f(n)) time} \}$

Polynomial Hierarchy $PH = \bigcup_i \bigcup_k \Sigma_i TIME(n^k) =\bigcup_i \bigcup_k \Pi_i TIME(n^k)$

$P \subseteq NP, Co-NP \subseteq \Sigma_2, \Pi_2 \subseteq \Sigma_3, \Pi_3 \subseteq \dots \subseteq PH$

Observe that any language in the Polynomial Hierarchy can be decided by a TM using polynomial space by considering every possible combination of variables that satisfy the quantified formula. Thus, $PH \subseteq PSPACE$.