NP versus co-NP
If a yes-answer to a problem can be checked quickly, can a no-answer always be checked quickly too?
Summary
Why it is open
NP is the class of decision problems whose "yes" instances have short certificates that can be checked in polynomial time; co-NP consists of their complements, the problems whose "no" instances have such certificates [2]. Satisfiability of a Boolean formula is NP-complete, and its complement, unsatisfiability, is co-NP-complete [2]. NP = co-NP would mean that there are always short proofs of unsatisfiability, or of the absence of a Hamiltonian cycle in a graph, even if such proofs are hard to find [2].
The question is closely tied to P versus NP. If P = NP, then NP = co-NP, so a proof that NP ≠ co-NP would also prove P ≠ NP; a world with NP = co-NP but P ≠ NP is conceivable [2] (see the Papex page P versus NP). If NP = co-NP, the polynomial hierarchy, a tower of classes built on NP and co-NP, collapses to NP [2]. Scott Aaronson lists NP ≠ co-NP as a conjecture that generalises P ≠ NP [2].
In 1979 Stephen Cook and Robert Reckhow turned the question into one about proofs. They defined a proof system for a set as any polynomial-time computable function onto that set, its input being a proof of its output, and showed that NP is closed under complement exactly when the set of tautologies has a polynomially bounded proof system: one in which every tautology has a proof of length polynomial in its own length [1]. NP = co-NP would therefore follow from a single such system, while NP ≠ co-NP needs super-polynomial lower bounds for every proof system in this general sense [1, 2]. Cook and Reckhow noted that the smallest known upper bound on proof length was exponential "no matter what the proof system" [1]. Aaronson notes that circuit lower bounds "tend to be somewhat easier than the analogous proof complexity lower bounds" [2]. No prize is attached; this page's status follows the Wikipedia list of unsolved problems in computer science, which includes the "NP = co-NP problem" [14].
What is known
Proof systems compared (1979). Cook and Reckhow showed that all standard Hilbert-style ("Frege") systems and natural deduction systems are equivalent up to a polynomial in minimum proof length, and introduced extended Frege systems, which allow abbreviations for formulas [1]. Frege systems are the standard textbook systems, typically with modus ponens as the only rule; in 2021 Sam Buss and Jakob Nordström described them as strictly stronger than resolution, with extended Frege conjectured to be stronger still [9].
Resolution (1985–1988). Resolution refutes an unsatisfiable formula, given as a list of clauses (ORs of variables and their negations), by repeatedly combining two clauses into a new one until it derives the empty clause [2]. In 1985 Armin Haken proved that formulas expressing the pigeonhole principle, that n + 1 pigeons cannot be placed in n holes without two sharing a hole, need resolution refutations of length exponential in n [2, 3, 9]. Alasdair Urquhart proved exponential lower bounds in 1987 for formulas built from expander graphs by Tseitin's method, which have polynomial-length proofs in a standard axiomatic propositional calculus [4, 9]. Vašek Chvátal and Endre Szemerédi showed in 1988 that randomly chosen sets of k-clauses (k ≥ 3) with enough clauses are almost surely unsatisfiable and need exponentially long resolution refutations [5, 9]. Because the search tree of a DPLL algorithm, a SAT method that prunes a tree of possible assignments, yields a resolution proof when the formula is unsatisfiable, such bounds also show that these algorithms need exponential time on some formulas [2]. Modern clause-learning (CDCL) solvers that make the right choices can match resolution up to a polynomial factor, and resolution length bounds their running time from below [9].
Stronger systems (1995–2017). Bounded-depth Frege systems limit the depth of the formulas in a proof; they are stronger than resolution and weaker than Frege [9]. Jan Krajíček, Pavel Pudlák and Alan Woods proved lower bounds of the form exp(n^(ε_d)) for pigeonhole tautologies at each depth d, which they described in 1995 as the largest lower bound "for the strongest proof system, for which any superpolynomial lower bounds are known" [6]. Toniann Pitassi, Paul Beame and Russell Impagliazzo proved similar bounds, and both works improved earlier lower bounds of Miklós Ajtai from 1988 [9]. In 1997 Pudlák proved an exponential lower bound for cutting planes, a system that reasons with linear inequalities, by extracting from any short refutation of certain formulas a small monotone circuit, which may compute with real numbers, and proving lower bounds for such circuits [7, 9]. Exponential cutting-planes lower bounds for random formulas with clauses of logarithmic width followed in 2017 [9]. Frege systems, by contrast, have polynomial-size proofs of the pigeonhole principle, as Buss showed in 1987 [9].
Limits of the methods (2000–2021). In 2000 María Luisa Bonet, Pitassi and Ran Raz showed that, unless factoring is feasible for the special case of Blum integers, neither Frege nor even the weaker TC0-Frege has the feasible interpolation property, so the interpolation method, which turns short proofs into small circuits, "cannot be used to obtain lower bounds" for them [8] (see Complexity of integer factorisation). Albert Atserias and Moritz Müller proved, in a paper published in 2020, that finding a resolution refutation at most polynomially longer than the shortest one is NP-hard [10]. In their 2021 survey Buss and Nordström list as open even a conditional exponential lower bound for Frege proofs from an assumption weaker than NP ≠ co-NP [9].
A conditional route (2026). In a paper published in May 2026, Krajíček proved that a hypothesis about strong proof systems, which follows from the existence of hard one-way permutations, implies NP ≠ co-NP, using an assumption about extensions of models of bounded arithmetic that he says "is open at present" [11] (see Existence of one-way functions).
Recent claims. Lew Gordeev and Edward Hermann Haeusler, who had claimed a proof of NP = PSPACE in the Bulletin of the Section of Logic in 2020, published an addendum there in 2022 claiming a proof of the weaker statement NP = co-NP, by compressing tree-like natural-deduction refutations of the existence of Hamiltonian cycles [12]. In a December 2022 preprint, not peer reviewed, Michael Chavrimootoo, Ethan Ferland, Erin Gibson and Ashley Wilson argue that the polynomial bound on proof size on which the NP = PSPACE argument depends "has not been correctly established", because the construction covers only minimal implicational logic; the preprint does not discuss the 2022 addendum [13]. On 15 October 2026 the Wikipedia list still included the problem [14].
Main approaches
Lower bounds for ever stronger systems. Prove super-polynomial lower bounds for one proof system after another, moving up from resolution towards Frege [1, 9]. Strongest evidence: exponential bounds for resolution, bounded-depth Frege and cutting planes [3, 4, 5, 6, 7]. Main difficulty: each bound covers one system, while NP ≠ co-NP needs all of them [1]; even a conditional exponential bound for Frege from an assumption weaker than NP ≠ co-NP is open [9].
Interpolation. Turn short refutations of specially built formulas into small circuits, then apply circuit lower bounds [7, 9]. Strongest evidence: Pudlák's cutting-planes bound [7]. Main difficulty: for Frege and TC0-Frege the method fails unless factoring is feasible for Blum integers [8].
Hard formula families. Find tautologies that defeat strong systems. Strongest evidence: random k-CNF formulas, random sets of clauses with k variables each, are hard for resolution [5], and in 2021 they were the only family discussed by Buss and Nordström for which polynomial-size Frege proofs were not known; the usual conjecture is that none exist [9]. Main difficulty: cutting-planes lower bounds for random formulas of constant clause width were still open in 2021 [9].
Logic and bounded arithmetic. Relate proof systems to weak theories of arithmetic and to cryptographic assumptions. Strongest evidence: Krajíček's 2026 conditional route from hard one-way permutations to NP ≠ co-NP [11]. Main difficulty: it rests on a model-theoretic assumption that is open [11].
Open sub-questions
- Random formulas in cutting planes. Do cutting-planes refutations of random k-CNF formulas need super-polynomial length for some constant k ≥ 3 [9]?
- A conditional Frege bound. Can an exponential lower bound for Frege proofs be derived from an assumption weaker than NP ≠ co-NP, for instance one about factoring, given that Bonet, Pitassi and Raz tie Frege interpolation to factoring [8, 9]?
- Parity gates. Are there super-polynomial lower bounds for bounded-depth Frege proofs extended with a parity (exclusive or) connective [9]?
- Random formulas in Frege. Do random k-CNF formulas have polynomial-size Frege refutations [9]?
- Model extensions. Does the assumption on extensions of models of bounded arithmetic in Krajíček's 2026 paper hold, so that his hypothesis (ST) implies NP ≠ co-NP without further assumptions [11]?
- Checking the addendum. Does the objection of Chavrimootoo and colleagues, that the construction covers only minimal implicational logic, also apply to the compressed Hamiltonian-cycle refutations of Gordeev and Haeusler's 2022 addendum [12, 13]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Cook, S. A. & Reckhow, R. A. (1979). The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44(1), 36–50. 10.2307/2273702 · Checked 15 Oct 2026
- Aaronson, S. (2016). P =? NP. In Open Problems in Mathematics, Springer, 1–122. 10.1007/978-3-319-32162-2_1 · Checked 15 Oct 2026
- Haken, A. (1985). The intractability of resolution. Theoretical Computer Science 39, 297–308. 10.1016/0304-3975(85)90144-6 · Checked 15 Oct 2026
- Urquhart, A. (1987). Hard examples for resolution. Journal of the ACM 34(1), 209–219. 10.1145/7531.8928 · Checked 15 Oct 2026
- Chvátal, V. & Szemerédi, E. (1988). Many hard examples for resolution. Journal of the ACM 35(4), 759–768. 10.1145/48014.48016 · Checked 15 Oct 2026
- Krajíček, J., Pudlák, P. & Woods, A. (1995). An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures & Algorithms 7(1), 15–39. 10.1002/rsa.3240070103 · Checked 15 Oct 2026
- Pudlák, P. (1997). Lower bounds for resolution and cutting plane proofs and monotone computations. Journal of Symbolic Logic 62(3), 981–998. 10.2307/2275583 · Checked 15 Oct 2026
- Bonet, M. L., Pitassi, T. & Raz, R. (2000). On interpolation and automatization for Frege systems. SIAM Journal on Computing 29(6), 1939–1967. 10.1137/S0097539798353230 · Checked 15 Oct 2026
- Buss, S. & Nordström, J. (2021). Proof complexity and SAT solving. In Handbook of Satisfiability, 2nd edn, IOS Press, chapter 7. 10.3233/FAIA200990 · Checked 15 Oct 2026
- Atserias, A. & Müller, M. (2020). Automating resolution is NP-hard. Journal of the ACM 67(5), 1–17. 10.1145/3409472 · Checked 15 Oct 2026
- Krajíček, J. (2026). On NP ∩ coNP proof complexity generators. Logical Methods in Computer Science 22(2), 14 (published 6 May 2026). 10.46298/lmcs-22(2:14)2026 · Checked 15 Oct 2026
- Gordeev, L. & Haeusler, E. H. (2022). Proof compression and NP versus PSPACE II: addendum. Bulletin of the Section of Logic 51(2), 197–205. 10.18778/0138-0680.2022.01 · Checked 15 Oct 2026
- Chavrimootoo, M. C., Ferland, E., Gibson, E. & Wilson, A. H. (2022). A closer look at some recent proof compression-related claims. Preprint, arXiv:2212.12150 (version 1, 23 December 2022), not peer reviewed. Source · Checked 15 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 15 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.