P versus NP problem
Let be a finite alphabet with at least two symbols and let be the set of finite strings over . A language is a subset . For a deterministic Turing machine with input alphabet , let be the set of strings on which halts in its accepting state, and let be the number of steps of on input . The worst-case running time is
runs in polynomial time if there is with for all .
- is the class of languages for Turing machines that run in polynomial time.
- A checking relation is a relation for some finite alphabet . It is polynomial-time if the language lies in , where is a new symbol.
- is the class of languages for which there are and a polynomial-time checking relation such that, for every ,
Every language in is in , so .
Problem. Determine whether
This is the formulation in Cook's official Clay problem description [1]. The answer does not depend on the choice of alphabet with , and the class is the same for all standard deterministic machine models. A solution is a proof of either or . Since Boolean satisfiability (SAT) is -complete [2, 3], the problem is equivalent to asking whether SAT is in . To prove , one must show that no polynomial-time Turing machine decides SAT.
Background
Polynomial time became the accepted formal notion of efficient computation in the 1960s. captures problems whose solutions can be verified efficiently once a short certificate is supplied. Cook [2] and, independently, Levin [3] proved that SAT is -complete: every language in reduces to SAT by a polynomial-time many-one reduction. Karp [4] then showed that 21 classical combinatorial problems, including clique, vertex cover and Hamiltonian cycle, are -complete. Thousands of problems are now known to be -complete, and a polynomial-time algorithm for any one of them would give one for all.
The question matters well beyond complexity theory. A proof of with a practical algorithm would break most public-key cryptography and would make finding proofs of bounded length as easy as checking them. The separation is widely believed, and it underlies modern cryptography as an assumption. [1, 9]
Equivalent formulations
The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every decision problem for which a proposed positive answer can be quickly verified can also be quickly solved.
source: Wikipedia
Let denote the class of problems solvable in polynomial time, and let denote the class of problems whose proposed solutions can be verified in polynomial time.
P versus NP conjecture.
This is a central question in computational complexity and an algebraic-complexity motivation for geometric complexity theory. It remains open.
source: J. M. Landsberg, “An introduction to geometric complexity theory”, arXiv:1509.02503 (2015).
References
- S. Cook, "The P versus NP problem", in J. Carlson, A. Jaffe and A. Wiles (eds.), The Millennium Prize Problems, Clay Math. Inst. and AMS (2006). Clay PDF
- S. A. Cook, "The complexity of theorem-proving procedures", Proc. 3rd Annual ACM Symposium on Theory of Computing (1971), 151–158. doi:10.1145/800157.805047
- L. A. Levin, "Universal sequential search problems", Problemy Peredachi Informatsii 9 (1973), no. 3, 115–116.
- R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, Plenum (1972), 85–103. doi:10.1007/978-1-4684-2001-2_9
- T. Baker, J. Gill and R. Solovay, "Relativizations of the question", SIAM J. Comput. 4 (1975), 431–442. doi:10.1137/0204037
- A. A. Razborov and S. Rudich, "Natural proofs", J. Comput. System Sci. 55 (1997), 24–35. doi:10.1006/jcss.1997.1494
- S. Aaronson and A. Wigderson, "Algebrization: a new barrier in complexity theory", ACM Trans. Comput. Theory 1 (2009), no. 1, 1–54. doi:10.1145/1490270.1490272
- R. Williams, "Nonuniform ACC circuit lower bounds", J. ACM 61 (2014), no. 1, 1–32. doi:10.1145/2559903
- S. Aaronson, "", in Open Problems in Mathematics, Springer (2016), 1–122. doi:10.1007/978-3-319-32162-2_1
- J. Håstad, "Almost optimal lower bounds for small depth circuits", Proc. 18th Annual ACM Symposium on Theory of Computing (1986), 6–20. doi:10.1145/12130.12132
- Wikipedia, P versus NP problem.
Source: Clay Mathematics Institute
Progress summary
The problem remains open: no accepted proof shows whether efficiently checkable problems can always be solved efficiently.
Cook established the central framework in 1971, and Karp showed in 1972 that many important problems are complete for this class. A polynomial-time algorithm for Boolean satisfiability would settle the question affirmatively, while proving no such algorithm exists would settle it negatively.
Known results
- by definition.
- Boolean satisfiability is -complete (Cook, 1971); Karp established twenty-one natural -complete problems (1972).
- Baker, Gill, and Solovay (1975) constructed oracle worlds with both and .
- Razborov–Rudich natural-proofs and Aaronson–Wigderson algebrization barriers exclude broad families of circuit and relativizing methods.
Current status (as of October 2026): and the completeness and barrier results are established, but neither nor has an accepted proof.
Solutions 1
Solution to the P vs. NP problem, based on arguments that resolve previously demonstrated methods and theorems.See full solution
Notes: Excludes about 7 conversations with ChatGPT, so it's just Gemini.
- MANUSCRITO CIENTÍFICO OFICIAL.pdfOpen