Turn your problem into a solved one

Computing · Algorithms & Data Structures · ages 21-22

Name ______________________ Date ____________

A bipartite graph has V vertices and E edges. What is the tightest worst-case construction bound for its matching-to-flow network when each adjacency-list vertex and edge is created once?
- O(V + E)
- O(VE + V^2)
- O(2^(V + E))
A decision-problem reduction converts every input of A to an input of B with the same yes-or-no answer. What does this let you do?
- Answer B by running A without any reverse conversion
- Prove both problems have polynomial algorithms immediately
- Convert A's input and use B's solver to answer A
A polynomial-time answer-preserving reduction to a decision problem with a polynomial-time solver gives a polynomial-time solver for the source problem.
Circle one: True False
Suppose decision problem A has no deterministic polynomial-time algorithm, and A reduces to B in polynomial time. What follows?
- B has no such algorithm
- B must have a deterministic polynomial-time algorithm
- A must have no correct decision algorithm at any runtime
For input length n >= 2, conversion takes exactly n^4 steps, including writing n^3 symbols. The target solver takes exactly m^2 steps on length m. Ignoring answer-copy time, how many steps do conversion and solving take together?
- n^4 + n^5 steps
- n^4 + n^6 steps
- n^4 + n^9 steps
A conversion takes exactly 2^n steps and writes at most n^2 symbols. The target solver is polynomial. Why does this combined algorithm have no polynomial runtime bound?
- The target solver must reject every converted input
- A polynomial solver requires its input length to be constant
- Conversion already takes exponential time
A scheduling problem reduces in polynomial time to B. Suppose B has no polynomial-time algorithm. Does this prove scheduling has no polynomial-time algorithm?
- No; this direction does not transfer that lower bound
- Yes; every source inherits the target's lower bound automatically
- Yes; every polynomial reduction rules out polynomial algorithms
A student reduces a problem with a polynomial-time solver to a new problem N in polynomial time and concludes N has a polynomial-time solver. Which response is justified?
- A reduction from an easy source always supplies its target's solver
- The reduction does not supply a solver for N
- Every polynomial reduction gives polynomial solvers for both problems

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

O(V + E) · The network has V + 2 vertices and E + V edges. Constant work per created vertex or edge gives the tightest listed bound O(V + E).
Convert A's input and use B's solver to answer A · The converted B input has the same answer as the original A input. A correct B solver therefore supplies A's answer.
True · Conversion takes polynomial time and writes a polynomial-length input. Applying the target's polynomial bound keeps the combined runtime polynomial.
B has no such algorithm · A polynomial B solver combined with the reduction would give a polynomial A solver, contradicting the stated assumption.
n^4 + n^6 steps · The target length is m = n^3, so solving takes (n^3)^2 = n^6 steps. Add the n^4 conversion steps, which already include writing the output.
Conversion already takes exponential time · The target solver's work is polynomial in n, but this algorithm still spends 2^n steps performing the conversion.
No; this direction does not transfer that lower bound · An easy source can reduce to a difficult target. To transfer B's lower bound to scheduling, a suitable reduction must go from B to scheduling.
The reduction does not supply a solver for N · The conversion would use an N solver to answer the source. Having a source solver does not reverse that conversion.