Reduction Between Problems

Definition

A technique of relating the hardness of problems: proving that solving one problem efficiently would let you solve many others, thereby 'passing the blame' and demonstrating fundamental difficulty rather than personal failure. The basis of NP-completeness.

Cast within

No topic-region cast yet — this appears once Reduction Between Problems's compiled claims are aligned into a topic region's argument tree.

Claims mentioning Reduction Between Problems (2)

Your notes

Loading notes...