A researcher proves that problem A polynomial-time many-one reduces to problem B. Which conclusion is valid?
AIf A is in P, then B is in P
BIf B is in P, then A is in P
CIf A is NP-complete, then B is also NP-complete
DBoth A and B must be in NP
A reduces to B means: given any instance of A, we can transform it into an instance of B in polynomial time, preserving yes/no answers. Therefore, if B has an efficient solver, we can solve A efficiently: apply the reduction function, then call B's solver. So B in P implies A in P. Option A is backwards — A being easy tells us nothing about B. Option C is close but incomplete: if A is NP-hard and A reduces to B, then B is NP-hard; but NP-completeness also requires B to be in NP, which isn't implied by the reduction alone.
Question 2 Multiple Choice
To prove that INDEPENDENT SET is NP-hard, a researcher performs a reduction. What is the correct direction, and what does a successful reduction prove?
AINDEPENDENT SET reduces to 3-SAT (a known NP-complete problem), proving INDEPENDENT SET is in P
B3-SAT reduces to INDEPENDENT SET, proving that if INDEPENDENT SET could be solved efficiently, 3-SAT could too — so INDEPENDENT SET is at least as hard as 3-SAT
C3-SAT reduces to INDEPENDENT SET, proving that 3-SAT is NP-hard because INDEPENDENT SET is already a hard problem
DThe direction does not matter; a reduction between any two problems proves they are equally hard
To prove B (INDEPENDENT SET) is NP-hard, you reduce a known NP-hard problem A (3-SAT) TO B. The logic: if there were an efficient algorithm for B, the reduction would give an efficient algorithm for A, contradicting A's NP-hardness. Therefore B must be hard too. Reducing in the other direction (B to A) would only prove A is at least as hard as B, which we already knew. Option D is a common misconception: direction matters critically. 'A reduces to B' and 'B reduces to A' have completely different implications.
Question 3 True / False
If problem A polynomial-time reduces to problem B, then A is harder than B.
TTrue
FFalse
Answer: False
The reduction shows A is *no harder than* B — not that A is harder. If A reduces to B, it means B is at least as capable as A: any efficient solver for B can solve A via the reduction. B is the 'harder' one (at least as hard as A). The confusion is common because reductions feel like they put A 'on top of' B, but the hardness flows the other way: the target of the reduction (B) is the one that must be powerful enough to handle the source (A).
Question 4 True / False
The 'many-one' in polynomial many-one reduction means the reduction function f should map different instances of A to different instances of B (i.e., f should be injective).
TTrue
FFalse
Answer: False
'Many-one' means the opposite: multiple different inputs to A can map to the same input for B — f need not be injective, and often isn't. The 'many-to-one' mapping is what gives the name. The only requirements are that f is polynomial-time computable and that x ∈ A ⟺ f(x) ∈ B. The function can collapse many distinct A-instances to the same B-instance. Bijectivity (one-to-one and onto) would be a Turing reduction or an isomorphism, which is a strictly stronger notion than many-one reduction.
Question 5 Short Answer
Explain why it matters that the reduction function f in a polynomial many-one reduction runs in polynomial time.
Think about your answer, then reveal below.
Model answer: The purpose of the reduction is to transfer complexity-theoretic hardness between problems. If an efficient solver for B exists and A reduces to B, the reduction gives an efficient algorithm for A: compute f(x) in polynomial time, then run B's solver in polynomial time, totaling polynomial time for A. If f took exponential time, this argument breaks down — the combined cost would be exponential regardless of B's efficiency, and the reduction would be useless for proving A is polynomially solvable. Similarly, if we are trying to prove B is NP-hard by reducing a known NP-hard problem A to B, an exponential-time f would not demonstrate that B is inherently hard — you could already solve A with brute force in that time. The polynomial bound on f is what makes the reduction meaningful as a hardness argument.
Polynomial time is the class boundary that complexity theory cares about. The reduction must preserve this boundary: transforming the question from 'is A hard?' to 'is B hard?' only works if the transformation itself is cheap (polynomial).