Questions: The P Versus NP Problem: Central Open Question

Question 1

A computer scientist announces a verified polynomial-time algorithm that solves Boolean satisfiability (SAT). What would this imply for complexity theory?

• A. It would prove P ≠ NP, since SAT was previously believed to be intractable and solving it efficiently confirms that barrier
• B. It would prove P = NP, because SAT is NP-complete — every NP problem reduces to SAT in polynomial time, so a polynomial SAT solver gives a polynomial solver for all of NP
• C. It would prove only that SAT ∈ P, with no implications for other NP problems since each must be examined separately
• D. It would prove that NP is empty, since SAT is the canonical hardest problem and solving it collapses the complexity hierarchy

Answer: (B)

The Cook-Levin theorem established that SAT is NP-complete: it is in NP, and every other problem in NP reduces to it in polynomial time. This means SAT is a 'hardest' problem in NP — if SAT ∈ P, then by the polynomial reductions, every problem in NP is also in P, so P = NP. This is exactly why SAT is the canonical target: a polynomial algorithm for SAT would immediately give polynomial algorithms for all NP problems, including graph coloring, integer programming, and protein folding.

Question 2

A problem can be solved in O(n³) time. Which complexity classes does it belong to?

• A. NP only — it is too slow for P, which requires linear or near-linear time
• B. Both P and NP — since it can be solved in polynomial time, it is in P, and since P ⊆ NP, it is also in NP
• C. P only — problems in NP must be unsolvable in polynomial time by definition
• D. Neither P nor NP — P requires linear time and NP requires exponential time in the worst case

Answer: (B)

P is the class of problems solvable in polynomial time — any polynomial, including O(n³). NP is the class of problems whose solutions are verifiable in polynomial time. Since P ⊆ NP (if you can solve a problem efficiently, you can verify a solution by re-solving it), any problem in P is automatically in NP. The misconceptions in the other options reflect very common confusions: P is not restricted to linear time, and NP does not mean 'exponential time' or 'hard.' Some NP problems are easy — they are also in P.

Question 3

Every problem in P is also in NP, because an efficient algorithm for solving a problem can trivially serve as a verification algorithm.

• T. True
• F. False

Answer: True

This is why P ⊆ NP is a theorem, not a conjecture. Given a proposed solution to a problem in P, you can verify it by simply running the polynomial-time solving algorithm on the input — if it produces the same answer, the solution is verified. More formally, a polynomial-time solver can be used as a polynomial-time verifier (ignore the proposed solution and just solve directly). This makes the containment P ⊆ NP immediate. The open question is whether the reverse holds: is NP ⊆ P, i.e., does every NP problem also have a polynomial solving algorithm?

Question 4

'NP' stands for 'not polynomial,' referring to the class of problems that can seldom be solved in polynomial time.

• T. True
• F. False

Answer: False

'NP' stands for 'nondeterministic polynomial time' — it refers to problems solvable in polynomial time on a nondeterministic Turing machine, which is equivalent to saying problems whose solutions can be verified in polynomial time on a deterministic machine. The name has nothing to do with infeasibility or the absence of polynomial algorithms. Many NP problems are in P — they have efficient algorithms. The confusion between 'NP' and 'exponentially hard' or 'not polynomial' is one of the most common misconceptions in complexity theory.

Question 5

In your own words, explain what the P vs. NP question is asking and why the ability to verify a solution efficiently does not obviously imply the ability to find one efficiently.

Model answer: The question asks: if checking whether a candidate answer is correct can be done in polynomial time, must finding a correct answer also be doable in polynomial time? Intuitively, checking a solution and finding one seem like fundamentally different tasks — checking a completed Sudoku is easy (verify each row, column, and box), but filling one in from scratch appears much harder. The asymmetry is that verification can exploit the structure of a given solution, while search must navigate an exponentially large space of candidates with no shortcut. P = NP would mean this intuition is wrong; P ≠ NP would confirm it.

The difficulty of proving P ≠ NP (despite most experts believing it) illustrates how hard it is to prove negative results in complexity theory — showing that no efficient algorithm can exist requires ruling out every possible algorithmic approach, including ones we haven't invented yet. The problem remains open because our mathematical tools for proving lower bounds (that problems require at least X resources) are far weaker than our tools for proving upper bounds (exhibiting an algorithm that uses at most X resources).