The golden ticket. P, NP, and the search for the impossible

DOI10.1515/9781400846610zbMATH Open1267.68003OpenAlexW4230365262MaRDI QIDQ4912935FDOQ4912935

Authors: Lance Fortnow 

Publication date: 2 April 2013

Full work available at URL: https://doi.org/10.1515/9781400846610

Recommendations

• The nature of computation
• The \(\text{P}=\text{NP}\) question and Gödel's lost letter
• In pursuit of the traveling salesman. Mathematics at the limits of computation
• Limits of computation. An introduction to the undecidable and the intractable
• \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective

zbMATH Keywords

computational complexitycomplexity theoryNP-completenesscryptographyproblem analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) History of computer science (68-03) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (6)

• In pursuit of the traveling salesman. Mathematics at the limits of computation
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Tensors in computations
• Algorithmic barriers falling: P = NP? A conversation with Donald E. Knuth conducted by Edgar G. Daylight on 18 June 2014 in Paris. Edited by Kurt De Grave
• Quantum walk public-key cryptographic system
• People, problems, and proofs. Essays from Gödel's lost letter: 2010

This page was built for publication: The golden ticket. P, NP, and the search for the impossible

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4912935)