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

Quantifiers, memory and randomness

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

  1. A decision problem accepts exactly when, for every polynomial-length X, there exists polynomial-length Y with R(input, X, Y) true. R is deterministic polynomial time. What follows?

    • Membership in Pi_2^P
    • Membership in P without any further argument
    • Membership outside every fixed level of PH

  2. What resource does membership in PSPACE bound by a polynomial in input length?

    • Running time, with no restriction on working memory
    • Working memory
    • Working memory by a fixed constant for every input length

  3. P = BPP is an unproved conjecture that every bounded-error randomized polynomial-time decision problem also has a deterministic polynomial-time algorithm.

    Circle one:   True   False

  4. Suppose PH = Sigma_2^P. What follows for a problem known to belong to Sigma_3^P?

    • It becomes undecidable under the assumed collapse
    • It also belongs to Sigma_2^P
    • It loses every algorithm that previously decided it

  5. An input is accepted exactly when there exists X such that for every Y there exists Z with R(input, X, Y, Z) true. All strings have polynomial length bounds and R is polynomial time. What follows?

    • Membership in Sigma_1^P from this representation alone
    • Membership in Pi_2^P from this representation alone
    • Membership in Sigma_3^P

  6. A decision problem accepts exactly when there exists a polynomial-length plan passing a deterministic polynomial-time check. Which membership follows?

    • The problem is proved NP-complete
    • The problem belongs to NP
    • The problem lies outside every fixed level of PH

  7. P is already contained in BPP. Which result would establish P = BPP?

    • Derandomize one selected BPP algorithm and stop there
    • Show that hardware can generate random bits more quickly
    • Prove every BPP problem belongs to P

  8. A problem has five alternating bounded quantifier blocks over nonempty domains. Its final predicate always returns true and ignores every quantified string. The problem is in P. What follows about PH?

    • No collapse follows from this example
    • PH must collapse to its second level from this example
    • Every fifth-level problem must have a polynomial-time solver
LightMySky · lightmysky.comW1-mt_ADfgl9UGpO-s1

Answer key

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

Quantifiers, memory and randomness W1-mt_ADfgl9UGpO-s1

  1. Membership in Pi_2^P · There are two alternating blocks starting universally. They provide a Pi_2^P membership bound.
  2. Working memory · PSPACE requires polynomial working space. It does not require polynomial running time.
  3. True · BPP uses polynomial time with error probability at most 1/3 on every input. The conjecture would place all of BPP in P.
  4. It also belongs to Sigma_2^P · Sigma_3^P is part of PH. The assumed equality therefore gives the problem membership in Sigma_2^P too.
  5. Membership in Sigma_3^P · Three alternating blocks start existentially. They provide a Sigma_3^P bound, not a proof of a minimum level.
  6. The problem belongs to NP · The plan is a short yes certificate and the check is a polynomial-time verifier. This establishes NP membership.
  7. Prove every BPP problem belongs to P · Equality needs both containments. The missing general containment is BPP inside P.
  8. No collapse follows from this example · The predicate always accepts and the domains are nonempty, so this is an always-yes problem. Unused quantifiers do not establish higher-level hardness.
Worksheet · LightMySky