Questions: Computability and Complexity: Overview and Connections

Question 1

A researcher proves that a decision problem Q is NP-complete. What does this tell us about whether Q can be solved at all?

• A. Q is undecidable — no algorithm can solve it
• B. Q is decidable but requires exponential time
• C. Q is decidable — NP-complete problems have algorithms, just not ones known to run in polynomial time
• D. Q is in P if and only if P = NP

Answer: (C)

NP-complete problems are decidable — they sit inside the decidable region, within the class NP. Algorithms that verify a solution in polynomial time are a prerequisite for NP membership, and exhaustive search algorithms can in principle solve them (just not efficiently). NP-completeness says nothing about undecidability; it is a statement about where a problem sits within the complexity hierarchy of solvable problems. Conflating 'no known efficient solution' with 'no solution at all' is the key misconception this question targets. Option D is partially true but incomplete — it describes what a proof that P = NP would imply, not what NP-completeness alone tells us.

Question 2

The halting problem is difficult to solve efficiently — it requires super-polynomial time.

• T. True
• F. False

Answer: False

The halting problem is not merely difficult to solve efficiently — it is impossible to solve at all. No algorithm exists that correctly answers 'does this program halt on this input?' for all possible program-input pairs. This is an undecidability result, proved by diagonalization, not a complexity result. Saying it 'requires super-polynomial time' implies that a slow algorithm exists, which is false. Undecidable problems are entirely outside the decidable region; complexity theory's classifications (P, NP, EXPTIME) only apply within it.

Question 3

Any problem that requires more than polynomial time to solve should be undecidable.

• T. True
• F. False

Answer: False

Many decidable problems require exponential time or more — they are in EXPTIME or higher complexity classes but are still decidable. For example, deciding the winner in certain board games (like generalized chess) requires exponential time in the board size but is perfectly decidable. Undecidability means no algorithm exists at all, regardless of time. The complexity hierarchy maps the structure of decidable problems by resource requirements; undecidability is a separate, outer boundary. Conflating 'hard' with 'unsolvable' is the core misconception in computability vs. complexity.

Question 4

Computability theory and complexity theory both use reductions as a key proof technique, even though they address different questions.

• T. True
• F. False

Answer: True

Reductions are the universal tool for comparing problem difficulty in both fields. In computability, many-one reductions show relative undecidability: if problem A reduces to B (A ≤_m B) and A is undecidable, then B is also undecidable. In complexity, polynomial-time reductions define NP-completeness: if A ≤_p B and A is NP-complete, then B is also NP-hard. Both uses share the same logical structure — 'if you could solve B, you could solve A, so B is at least as hard as A' — differing only in the resource constraints allowed for the reduction itself.

Question 5

Why is 'P vs. NP' a question about efficient computation rather than about what can be computed at all?

Model answer: P and NP are both subsets of the decidable problems — every problem in NP has an algorithm (verification is polynomial, and exhaustive search always terminates for decidable problems). The question P vs. NP asks whether problems whose solutions can be verified quickly can also be solved quickly — it is entirely about the efficiency of computation, not its existence. Undecidability is the outer boundary of what algorithms can do at all; P vs. NP concerns the inner structure of efficiently solvable problems within the decidable region. A problem like satisfiability (SAT) is NP-complete: it is decidable, but no polynomial-time algorithm is known. This is fundamentally different from the halting problem, for which no algorithm of any kind exists.

The mental map from the explainer is useful here: imagine problems arranged by solvability. Undecidable problems sit outside the decidable region entirely. P vs. NP is a question about where the boundary within the decidable region lies — specifically whether the efficiently-verifiable problems (NP) are also efficiently-solvable (P). The two questions are at completely different levels of the hierarchy.