ECCC-Report TR17-004https://eccc.weizmann.ac.il/report/2017/004Comments and Revisions published for TR17-004en-usSun, 08 Jan 2017 16:44:56 +0200
Paper TR17-004
| P=?NP |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2017/004In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, for a broad audience of mathematicians, scientists, and engineers. I offer a personal perspective on what it’s about, why it's important, why it's reasonable to conjecture that P!=NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems. The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.Sun, 08 Jan 2017 16:44:56 +0200https://eccc.weizmann.ac.il/report/2017/004