A Reduction Constructed

The Prompt

Choose a combinatorial problem of interest to you — a scheduling problem, a puzzle, a game-theoretic question — and construct a polynomial-time reduction from a known NP-complete problem (SAT, 3-SAT, CLIQUE, VERTEX COVER, or another from Karp's list) to your chosen problem, or vice versa. Document the reduction, prove its correctness, and reflect on what the reduction reveals about the structure your problem shares with the NP-complete canon.

Completion Criteria

A written reduction with a correctness argument, the source and target problems named, and a one-paragraph reflection on what the reduction disclosed about the structure of the problem.

Students who have attested

No Students have attested this quest yet. Be the first.