56. What is a polynomial-time reduction and why does it matter?
HardComplexity classes
Technical
Show model answer
A reduction transforms instances of problem A into instances of problem B in polynomial time so the answers match. If A reduces to B and B is easy, A is easy; if A is hard, B is at least as hard. To prove a new problem NP-complete, show it is in NP and reduce a known NP-complete problem to it.