Computation and complexity

P, NP, completeness, and the two different things "undecidable" is used to mean.

6 questions. Reveal each answer when you have committed to one.

1. P versus NP asks whether every problem whose yes-instances can be verified quickly can also be

   • Averified slowly
   • Bdecided quickly
   • Cwritten down
   • Dreduced to another problem
   Show the answer

   B. decided quickly

   The asymmetry is deliberate: NP concerns verifying yes-instances from a certificate. Whether no-instances are equally verifiable is the separate open question of NP versus co-NP. More on p versus np.

2. In complexity theory, "quickly" means

   • Ain linear time
   • Bin under one second
   • Cin polynomial time
   • Din constant time
   Show the answer

   C. in polynomial time

   The identification of polynomial time with efficiency is a convention rather than a fact — an algorithm running in n¹⁰⁰ steps is polynomial and useless. It earns its place because the class does not change under reasonable changes of machine model. More on polynomial time.

3. A problem is NP-complete when it lies in NP and

   • Ais undecidable
   • Bprovably requires exponential time
   • Chas no known algorithm
   • Devery problem in NP reduces to it in polynomial time
   Show the answer

   D. every problem in NP reduces to it in polynomial time

   That reduction is what makes the class tractable to reason about. Nothing is known to require exponential time here; if it were, P versus NP would be settled. More on np-complete.

4. A polynomial-time algorithm for a single NP-complete problem would

   • Aprove P = NP
   • Bprove P ≠ NP
   • Cchange nothing
   • Dprove the problem undecidable
   Show the answer

   A. prove P = NP

   Every NP problem reduces to it in polynomial time, so one fast algorithm would give fast algorithms for all of them. This is why thousands of unrelated problems stand or fall together. More on np-complete.

5. In computability, a problem is undecidable when

   • Anobody has solved it yet
   • Bno algorithm always halts with a correct answer
   • Cit is extremely difficult
   • Dit has no answer
   Show the answer

   B. no algorithm always halts with a correct answer

   Each input still has a correct answer. What is impossible is an algorithm producing it for every input. This is a different notion from a statement being undecidable in a theory, which is about axioms rather than algorithms. More on undecidability.

6. A decision problem is one whose answer for each input is

   • Aa proof
   • Ba number
   • Cyes or no
   • Da set
   Show the answer

   C. yes or no

   Complexity classes such as P and NP are defined over decision problems, which is why statements about them are phrased that way. It is rarely a real restriction, since a search problem can usually be recast as one. More on decision problem.