 $$P\mathop{ =}\limits^{?}NP$$Scott Aaronson ()
A chapter in Open Problems in Mathematics, 2016, pp 1-122 from Springer Abstract: Abstract In 1950, 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 $$\mathsf{P}\mathop{ =}\limits^{?}\mathsf{NP}$$ problem, and consider one of the great open problems of science. Here I survey the status of this problem in 2016, 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. Keywords: Circuit Lower Bounds; Mulmuley; Natural Proof; Arithmetic Circuits; Nondeterministic Time Hierarchy Theorem (search for similar items in EconPapers) There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-32162-2_1 Ordering information: This item can be ordered from DOI: 10.1007/978-3-319-32162-2_1 Access Statistics for this chapter More chapters in Springer Books from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.