The Lumenary · Advanced undergraduate

Computational complexity

Name: ______________________

Date: ______________________

You will learn to

Define running time, the classes P, NP and coNP, and place standard problems in them
Prove the inclusions $\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}$ and explain why $\mathrm{P} \ne \mathrm{EXPTIME}$ by the time hierarchy theorem
State the Cook–Levin theorem and explain the idea of its proof
Prove NP-completeness by polynomial-time reductions, including 3-SAT to independent set, vertex cover and clique
Explain what is known and unknown about P versus NP, and why cryptography rests on unproved hardness assumptions

1.
Which of these is the definition of the class NP?
- A.Decision problems whose "yes" instances have certificates of polynomial length that can be checked in polynomial time.
- B.Decision problems that cannot be solved in polynomial time.
- C.Decision problems whose "yes" and "no" answers both have short checkable certificates.
- D.Decision problems solvable in exponential time.
2.
Which of these problems are known to be in P? (Select all that apply.)
- A.Is a given graph 2-colourable?
- B.Is a given graph 3-colourable?
- C.Is a given $n$ -digit number prime?
- D.Does a given graph have a perfect matching?
- E.Does a given graph have a Hamiltonian cycle?
3.
Karp's reduction from 3-SAT to INDEPENDENT SET is applied to a 3-CNF formula with $7$ clauses on $5$ variables. How many vertices does the graph $G_\varphi$ have?
4.
In the reduction from SAT to 3-SAT, a clause $(\ell_1 \vee \ell_2 \vee \cdots \vee \ell_7)$ with $7$ literals is replaced by a chain of 3-literal clauses using fresh variables $z_1, z_2, \dots$ . How many 3-literal clauses does it become?
5.
You want to prove that a new problem $B \in \mathrm{NP}$ is NP-complete. Which is enough?
- A.Give a polynomial-time reduction $\mathrm{3\text{-}SAT} \le_p B$ .
- B.Give a polynomial-time reduction $B \le_p \mathrm{3\text{-}SAT}$ .
- C.Show that the best known algorithm for $B$ takes exponential time.
- D.Show that $B$ has exponentially many candidate solutions.
6.
In the proof of Theorem 5 ( $\Leftarrow$ direction) we said: an independent set $S$ of size $m$ in $G_\varphi$ contains exactly one vertex from each clause. Why?
- A.Each clause's three vertices form a triangle, so $S$ has at most one of them; with $m$ clauses and $|S| = m$ , it must have exactly one from each.
- B.Because complementary literals are joined by edges.
- C.Because $\varphi$ is satisfiable.
- D.Because every independent set of $G_\varphi$ has exactly $m$ vertices.
7.
Which of these statements are known theorems (not conjectures)? (Select all that apply.)
- A.If some NP-complete problem is in P, then $\mathrm{P} = \mathrm{NP}$ .
- B. $\mathrm{P} \ne \mathrm{EXPTIME}$ .
- C.If $\mathrm{P} = \mathrm{NP}$ then $\mathrm{NP} = \mathrm{coNP}$ .
- D.If factoring can be done in polynomial time, then $\mathrm{P} = \mathrm{NP}$ .
- E. $\mathrm{NP} \ne \mathrm{PSPACE}$ .
8.
The Lean file proves bruteForce_correct : bruteForce φ = true ↔ Satisfiable φ and length_allAssignments : (allAssignments n).length = 2 ^ n. Which conclusion do these two theorems justify?
- A.SAT is decidable, by an algorithm proved correct that examines exactly $2^n$ assignments.
- B.SAT is in P.
- C.SAT requires exponential time.
- D.Nothing: decide could prove satisfiability directly, so the theorems are vacuous.
9.
Implement Karp's reduction. A 3-CNF formula is a list of clauses, each a tuple of three nonzero integers ( $v$ for $x_v$ , $-v$ for $\neg x_v$ ). Number the vertices $3i + j$ for the $j$ -th literal ( $j = 0, 1, 2$ ) of clause $i$ . Write karp_graph(formula) returning the set of edges as pairs (p, q) with p < q: the three edges inside each clause, and an edge between every two vertices whose literals are complementary.
Computational — Practice

Answer key — Computational complexity

1.
NP is the class of decision problems $L$ for which there are a polynomial $q$ and a polynomial-time verifier $V$ with $x \in L \iff \exists y,\ |y| \le q(|x|),\ V(x, y) = 1$ . A satisfying assignment certifies satisfiability; a colouring certifies colourability. "NP" stands for nondeterministic polynomial time.
2.
2-colourability, primality (AKS) and perfect matching (Edmonds) are in P. 3-colourability and Hamiltonian cycle are NP-complete, so they are in P if and only if $\mathrm{P} = \mathrm{NP}$ .
3.
One vertex per literal occurrence: $7 \times 3 = 21$ vertices, forming $7$ triangles, plus edges between complementary literals. The formula is satisfiable iff the graph has an independent set of size $7$ .
4.
$(\ell_1 \vee \ell_2 \vee z_1) \wedge (\neg z_1 \vee \ell_3 \vee z_2) \wedge (\neg z_2 \vee \ell_4 \vee z_3) \wedge (\neg z_3 \vee \ell_5 \vee z_4) \wedge (\neg z_4 \vee \ell_6 \vee \ell_7)$ : $k - 2 = 5$ clauses with $k - 3 = 4$ fresh variables. It is satisfiable exactly when some $\ell_j$ can be made true.
5.
Reduce a known NP-complete problem to $B$ : $\mathrm{3\text{-}SAT} \le_p B$ . Then for any $L \in \mathrm{NP}$ , $L \le_p \mathrm{3\text{-}SAT} \le_p B$ , and together with $B \in \mathrm{NP}$ this makes $B$ NP-complete.
6.
The three vertices of a clause are pairwise adjacent, so an independent set contains at most one of them. There are $m$ clauses and $|S| = m$ , so by the pigeonhole principle every clause contributes exactly one vertex. The complementary-literal edges are then used for the next step: the chosen literals can all be true at once.
7.
(a), (b) and (c) are theorems. (d) does not follow from anything known: factoring is in $\mathrm{NP} \cap \mathrm{coNP}$ and is not believed NP-complete. (e) is open: $\mathrm{P} \ne \mathrm{EXPTIME}$ shows that at least one inclusion in $\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}$ is strict, but not which.
8.
They show that brute force is a correct decision procedure for SAT and that it inspects exactly $2^n$ assignments. They say nothing about polynomial time (b) and nothing about lower bounds (c); and they are not vacuous (d): they hold for every formula and are used to prove php32_unsat.

def karp_graph(formula):
    edges = set()
    n = 3 * len(formula)
    for p in range(n):
        for q in range(p + 1, n):
            same_clause = p // 3 == q // 3
            lp = formula[p // 3][p % 3]
            lq = formula[q // 3][q % 3]
            if same_clause or lp == -lq:
                edges.add((p, q))
    return edges

The graph has $3m$ vertices and at most $\binom{3m}{2}$ edges, so it is built in polynomial time. By Theorem 5, the formula is satisfiable iff this graph has an independent set of size $m$ .