P, NP and What NP-Complete Means · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Easy to Check, Hard to Solve

Computing · Algorithms & Data Structures · ages 21-22
Name ______________________   Date ____________

  1. For coloring a map with three colors, what is the certificate?

    • The count of regions on the map
    • The list of border lengths
    • A coloring in which neighbors differ

  2. What does it mean for a problem to be in NP?

    • A correct answer can always be found quickly
    • A proposed answer can be checked quickly
    • The problem has no correct answer at all

  3. Every NP-hard problem is also NP-complete.

    Circle one:   True   False

  4. Problem A reduces to problem B in polynomial time, and B gains a fast solver. What follows for A?

    • A is proved to have no solution
    • B is proved NP-complete
    • A gains a fast method through the translation

  5. You receive a three-coloring where two neighboring regions share a color. What follows?

    • This certificate fails, so it proves nothing about the map
    • The map must need a fourth color
    • Map coloring falls outside NP

  6. A team announces a polynomial algorithm for one NP-complete problem. What is the correct consequence?

    • Only that problem becomes easy and nothing else changes
    • Every problem in NP gains a polynomial method
    • Checking answers becomes slower than solving

  7. A puzzle admits no quick check for proposed solutions, yet every NP problem reduces to it. What is the right label?

    • In P
    • NP-hard
    • NP-complete

  8. A startup claims all NP-complete problems are easy because its solver is fast on customer inputs. What is wrong?

    • Fast on some inputs is not a polynomial method for every input
    • NP-complete problems accept no inputs
    • Customer inputs are always the hardest cases
LightMySky · lightmysky.comW1-mt_wwmNVG_VnB-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Easy to Check, Hard to Solve W1-mt_wwmNVG_VnB-s1

  1. A coloring in which neighbors differ · The coloring itself proves the answer is yes. Checking it means walking every border.
  2. A proposed answer can be checked quickly · NP is about checking speed, not solving speed. Finding the answer may still be slow.
  3. False · NP-complete also demands membership in NP. Without a quick check, a problem is only NP-hard.
  4. A gains a fast method through the translation · Translate A into B, solve with the fast method, and translate back. That is what a reduction buys.
  5. This certificate fails, so it proves nothing about the map · One bad coloring rejects only itself. Another coloring might still succeed.
  6. Every problem in NP gains a polynomial method · Every NP problem reduces to it, so the fast method travels along the reductions to all of NP.
  7. NP-hard · Hardness holds through the reductions, but membership in NP fails without a quick check.
  8. Fast on some inputs is not a polynomial method for every input · A polynomial method must be fast on every input with a proved bound. Good behavior on some inputs promises nothing.
Worksheet · LightMySky