Complexity Beyond NP: Space, Randomness and the Hierarchy · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Count the quantifiers, find the level

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

  1. A problem reads: for every X there is a Y such that the check passes. Which level?

    • Second level, above NP
    • Inside P
    • Unclassifiable without a machine

  2. What is NP in the larger landscape?

    • The hardest class known
    • One class among many
    • The union of all efficient classes

  3. Randomized polynomial time is widely believed to equal deterministic polynomial time.

    Circle one:   True   False

  4. The hierarchy collapses to the second level. What happens to a third-level problem?

    • It becomes unsolvable
    • It becomes solvable at the second level
    • It stays exactly where it is

  5. There is an X such that for every Y there is a Z with a fast check. Which level?

    • First
    • Second
    • Third

  6. There is a plan with an efficiently checkable test. Which class?

    • Undecidable
    • NP, the first level
    • Third level

  7. What would turn the belief about randomness into a theorem?

    • More alternations in the hierarchy
    • Faster coin flips in hardware
    • A proof giving every fast randomized algorithm a fast deterministic twin

  8. A four-alternation problem is placed at the second level. What follows?

    • The hierarchy collapses at least partially
    • The counting method was misapplied only
    • The problem leaves the hierarchy
LightMySky · lightmysky.comW1-mt_ADfgl9UGpO-s1

Answer key

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

Count the quantifiers, find the level W1-mt_ADfgl9UGpO-s1

  1. Second level, above NP · For-all then there-exists is one alternation past NP.
  2. One class among many · Space, randomness, and alternations all lie past it.
  3. True · The belief says randomness adds nothing.
  4. It becomes solvable at the second level · Collapse drags everything above down to it.
  5. Third · Two alternations climb two levels past the base.
  6. NP, the first level · One exists-quantifier over a fast check is NP.
  7. A proof giving every fast randomized algorithm a fast deterministic twin · Derandomization is the missing proof.
  8. The hierarchy collapses at least partially · A high problem sitting low flattens the levels.
Worksheet · LightMySky