Cook, Levin, and the Millennium

The Prompt

Explain the P vs NP problem to someone outside computer science. State the question precisely; give one concrete example of a problem in P and one in NP; explain what NP-completeness means and why it matters. Cite Cook's 1971 paper, Karp's 1972 list of twenty-one NP-complete problems, and the Clay Mathematics Institute's Millennium Prize designation. Conclude with a note on what the world would look like if P = NP.

Completion Criteria

A short essay (three or four paragraphs) with at least three citations, including Cook (1971) and Karp (1972), and a concluding note on the consequences of resolution.

Students who have attested

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