Self-Assessment Quiz: Introduction to Complexity Theory

Twenty questions to check your understanding. Answer before opening the key. Aim for 17+. The recurring trap in this chapter is the direction of reductions and the meaning of "NP" — several questions probe exactly those.

Question 1

A complexity class is best described as:

A) a set of algorithms that all run in the same time B) a set of decision problems solvable within a shared resource bound on a fixed model of computation C) the set of all problems a computer can solve D) a programming-language feature for measuring runtime

Question 2

The class P consists of decision problems solvable in:

A) constant time B) $O(n^k)$ time for some constant $k$ C) exponential time D) any finite time

Question 3

"NP" stands for:

A) non-polynomial B) nearly polynomial C) nondeterministic polynomial time D) not provable

Question 4

A problem is in NP if and only if its yes-instances have:

A) a polynomial-time algorithm that solves them B) a short (polynomial-size) certificate verifiable in polynomial time C) no solution at all D) an exponential-size proof

Question 5

Which relationship between P and NP is proven?

A) $\text{P} = \text{NP}$ B) $\text{P} \subsetneq \text{NP}$ C) $\text{P} \subseteq \text{NP}$ D) $\text{NP} \subseteq \text{P}$

Question 6

The notation $A \le_p B$ means:

A) $A$ is at least as hard as $B$ B) $B$ is no harder than $A$ C) $A$ is no harder than $B$ (a fast algorithm for $B$ yields one for $A$) D) $A$ and $B$ are the same problem

Question 7

A problem $H$ is NP-hard if:

A) $H \in \text{NP}$ and $H \in \text{P}$ B) every problem in NP reduces to $H$ in polynomial time C) $H$ reduces to some NP problem D) $H$ is the hardest problem ever encountered

Question 8

A problem is NP-complete if it is:

A) in NP only B) NP-hard only C) both in NP and NP-hard D) neither in P nor in NP

Question 9

To prove a new problem $B$ is NP-complete, the reduction must go:

A) from $B$ to a known NP-complete problem ($B \le_p \text{SAT}$) B) from a known NP-complete problem to $B$ ($\text{SAT} \le_p B$) C) in either direction; it does not matter D) from $B$ to a problem in P

Question 10

The Cook–Levin theorem states that:

A) $\text{P} = \text{NP}$ B) SAT is NP-complete C) the halting problem is undecidable D) every problem in NP is in P

Question 11

The historical importance of Cook–Levin is that it:

A) solved P vs. NP B) gave the first problem proven NP-complete directly, so all later ones follow by a single reduction C) proved SAT is in P D) showed reductions are unnecessary

Question 12

If a single NP-complete problem were shown to be in P, the consequence would be:

A) only that one problem becomes easy B) $\text{P} = \text{NP}$ (all of NP collapses into P) C) the halting problem becomes decidable D) nothing provable

Question 13

Which is in P, not NP-complete?

A) 3-SAT B) CLIQUE C) 2-SAT D) Hamilton circuit

Question 14

In the $\text{3-SAT} \le_p \text{CLIQUE}$ reduction, choosing one vertex per "column" corresponds to:

A) choosing one variable to delete B) choosing one literal to make true in each clause C) coloring the graph D) finding a Hamilton circuit

Question 15 (True/False, justify)

True or false: "This problem is in NP" is bad news that means the problem is intractable. Justify in one sentence.

Question 16 (True/False, justify)

True or false: The decision version and the optimization version of TSP "stand or fall together" with respect to polynomial-time solvability. Justify in one sentence.

Question 17 (True/False, justify)

True or false: Because SAT is NP-complete, no SAT instance with a million variables can ever be solved in practice. Justify in one sentence.

Question 18 (Short answer)

State the P versus NP question in one sentence, framed as a question about solving versus checking.

Question 19 (Short answer)

You have shown your problem is NP-complete. Name the three coping strategies of §37.6 and the single guarantee each one sacrifices.

Question 20 (Short answer)

In one sentence each, distinguish undecidable (Chapter 36) from intractable (this chapter).

Answer Key

Justifications for the True/False items. - Q15 (False): Every problem in P is also in NP, so "in NP" is not a hardness verdict; the genuinely hard members are the NP-complete ones not known to be in P. - Q16 (True): A polynomial decision algorithm + binary search over the budget $B$ yields a polynomial optimization algorithm, and a hardness result for the decision version dooms the optimization version — so they are equivalent in tractability. - Q17 (False): "NP-complete" is a statement about the worst case over all possible inputs; the formulas you actually encounter are typically far from worst-case, and industrial SAT solvers routinely dispatch millions of variables by exploiting that structure.

Topics to review by question