Reductions: Solving One Problem by Turning It into Another · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Turn your problem into a solved one

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

  1. Matching reduces to max flow with a small network build. What does the conversion cost?

    • Almost nothing beside building the network
    • More than solving the matching directly
    • An infinite amount of time

  2. You reduce problem A to problem B. What do you get?

    • Both problems disappear forever
    • A is proven harder than B
    • A solver for B now answers A

  3. A reduction must run quickly for its argument to mean anything.

    Circle one:   True   False

  4. Problem A reduces to problem B, and A is known hard. What follows?

    • B must be hard as well
    • B is easy, since reductions simplify
    • A becomes easy through B

  5. Problem A reduces to problem B, and B has a fast solver. What follows?

    • B is hard because A exists
    • A is easy too, by reusing B's solver
    • Nothing follows about either problem

  6. Why does a slow conversion void the whole argument?

    • Slow code is illegal
    • Fast solvers refuse slow inputs
    • The conversion cost swallows any savings from reuse

  7. You reduce a hard puzzle to scheduling and conclude scheduling is hard. A colleague says you proved scheduling is easy. Who is right?

    • You, since hardness travels backwards to the target
    • The colleague, since solvers transfer
    • Neither, since reductions say nothing

  8. A student reduces a known easy problem to their new problem and declares the new one easy. What is wrong?

    • Nothing, the direction is correct
    • The direction is backwards: easiness flows the other way
    • Reductions can only prove hardness
LightMySky · lightmysky.comW1-mt_PAwby3ZyAr-s1

Answer key

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

Turn your problem into a solved one W1-mt_PAwby3ZyAr-s1

  1. Almost nothing beside building the network · The build is cheap, so the flow solver does the real work.
  2. A solver for B now answers A · Conversion plus the target solver settles the source problem.
  3. True · A slow conversion swallows whatever the solver saves.
  4. B must be hard as well · Backwards reading transfers hardness from source to target.
  5. A is easy too, by reusing B's solver · Forwards reuse carries easiness from target to source.
  6. The conversion cost swallows any savings from reuse · Reuse only pays when converting stays cheap.
  7. You, since hardness travels backwards to the target · Hard source into scheduling means scheduling inherits the hardness.
  8. The direction is backwards: easiness flows the other way · Easy source to new target proves nothing; easy target to source is the useful way.
Worksheet · LightMySky