2 docs tagged with "np-completeness"

If you can solve one problem, can you solve another? Reductions are the tool that lets us answer that question precisely — and they are the key to everything in Phase 2.

In 1971, Stephen Cook proved that one specific problem sits at the top of the entire NP hierarchy — and that solving it would solve everything else. This is the result that launched the field of NP-Completeness.