The status of the P versus NP problem

2009/08/25 by Lance Fortnow · 5 citations
Computer Science · #Complexity and Algorithms in Graphs #Quantum Computing Algorithms and Architecture #Cryptography and Data Security

paper · doi:10.1145/1562164.1562186

openalex publication_date 2009/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/13

Abstract

It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• P = BPP if E requires exponential circuits
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Paths, Trees, and Flowers

Cited by

• Limits of Uniform Certification in the Standard Turing Model -- Semantic Invariants and Admissible Methods
• Logical Probability and the Strength of Mathematical Conjectures
• Computational hardness assumption [wikipedia]
• Conjecture [wikipedia]
• P versus NP problem [wikipedia]