Skip to interview prep
Apexed

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.

What is a polynomial-time reduction and why does it matter — Data structures & algorithms interview question — Apexed