P versus NP and the finite descriptive-complexity separations: NP versus co-NP ($\Sigma^1_1$ versus $\Pi^1_1$) and P versus $\Delta^1_1$ over finite structures

The source is temporarily unavailable. Showing a saved statement. Last verified: 2026-10-22

The classical complexity-theoretic containment chain $P \subseteq NP \cap coNP \subseteq NP$ is central to the theory of efficient computation, yet it is not known whether either inclusion is strict. The question arises here as the finite counterpart of separation theorems for infinite time Turing machines (machines running through transfinite ordinal time): while the infinitary analogues are settled ($P \ne NP$ and $P \ne NP \cap coNP$ for infinite time Turing machines, and $D \ne ND \cap coND$ for nondeterministic infinite time Turing machines), Carmody (2023) explicitly notes that the finite analogues remain open. The problem is to determine which of the inclusions $P \subseteq NP \cap coNP \subseteq NP$ are strict: whether $P \ne NP$ (the Clay Millennium Prize question), whether $NP \ne coNP$ — equivalently, by Fagin's theorem, whether the existential and universal second-order logic classes $\Sigma^1_1$ and $\Pi^1_1$ differ over finite structures — and whether $P \ne NP \cap coNP$, equivalently whether $P$ is a proper subclass of $\Delta^1_1$ over finite structures. All three questions remain open.

Background

A Turing machine is the standard mathematical model of an algorithm; a deterministic machine has a single transition at each step, while a nondeterministic machine may branch into several possible transitions and is said to accept an input if at least one branch leads to acceptance. $P$ is the class of decision problems solvable by a deterministic Turing machine in time bounded by a polynomial in the input length, and $NP$ is the class solvable by a nondeterministic machine in polynomial time — equivalently, the class of problems whose proposed solutions can be verified in polynomial time, such as Boolean satisfiability (SAT). $coNP$ is the class of complements of $NP$ problems. It is elementary that $P \subseteq NP \cap coNP \subseteq NP$, and it is open whether either inclusion is an equality. The strictness of the containment $P \subseteq NP$, $P \ne NP$, is the famous P versus NP problem, posed in the early 1970s and designated a Millennium Prize Problem by the Clay Mathematics Institute, which lists it as unsolved (accessed 2026-08-28); decades of surveys (Fortnow 2009, 2022) record no accepted proof in either direction. Progress on the finer separations is equally blocked: no proof of $NP \ne coNP$ or of $P \ne NP \cap coNP$ is known, and conversely no equality is known either (for example, integer factorization lies in $NP \cap coNP$ but is not known to be in $P$). These questions have an equivalent logical form via descriptive complexity theory, the study of which classes of finite structures are definable in which logics. A finite structure is a finite universe with interpretations of the relation, function, and constant symbols of a vocabulary; second-order logic extends first-order logic by allowing quantification over relations and functions on the structure. $\Sigma^1_1$ consists of the properties definable by an existential second-order sentence (a prefix of existential second-order quantifiers followed by a first-order formula), $\Pi^1_1$ the dual universal form, and $\Delta^1_1$ the properties definable in both. Fagin's theorem (1974) states that over finite structures $NP$ is exactly the class of properties definable in $\Sigma^1_1$ existential second-order logic; consequently $coNP = \Pi^1_1$ and $NP \cap coNP = \Delta^1_1$ over finite structures, and $P \subseteq \Delta^1_1$. Thus $NP$ versus $coNP$ is exactly the question whether $\Sigma^1_1 \ne \Pi^1_1$ over finite structures, and $P$ versus $NP \cap coNP$ is exactly whether $P$ is a proper subclass of $\Delta^1_1$ over finite structures; the standard treatment is in Libkin's textbook (2004). The infinitary analogue of this circle of questions is settled. Infinite time Turing machines, introduced by Hamkins and Lewis (2000), are Turing machines whose computations extend through transfinite ordinal time, with a special limit rule for the machine state and tape contents at limit stages. For these machines, Schindler (2003) proved $P \ne NP$, and Deolalikar, Hamkins, and Schindler (2005) proved $P \ne NP \cap coNP$. Carmody (2023) introduced nondeterministic infinite time Turing machines and proved the main theorem $D \ne ND \cap coND$, where $D$ is the class of sets decidable by an infinite time Turing machine and $ND$ the class recognizable by a nondeterministic one. The infinitary proofs proceed by identifying $ND$ with the pointclass $\Sigma^2_1$ and $coND$ with $\Pi^2_1$ (a pointclass is a class of definable sets of reals; $\Sigma^2_1$ and $\Pi^2_1$ are the second-order levels of the projective hierarchy, the analogues one type level up of $\Sigma^1_1$ and $\Pi^1_1$) and using the classical set-theoretic fact $\Sigma^2_1 \ne \Pi^2_1$; as Carmody (2023) explains, this strategy has no finite counterpart, because whether $\Sigma^1_1 \ne \Pi^1_1$ over finite structures is precisely one of the unresolved finite questions.

Problem Statement

Determine the containment structure of the chain

$P \subseteq NP \cap coNP \subseteq NP$

i.e., for each of the inclusions $P \subseteq NP \cap coNP$ and $NP \cap coNP \subseteq NP$ (and hence the inclusion $P \subseteq NP$), decide whether it is an equality or a strict inclusion. Concretely, answer the three classical questions: (1) Is $P \ne NP$ — the P versus NP Millennium Prize problem in its standard formulation: does there exist a language decidable by a nondeterministic Turing machine in polynomial time but not by any deterministic Turing machine in polynomial time? (2) Is $NP \ne coNP$ — equivalently, by Fagin's theorem, do the existential second-order class $\Sigma^1_1$ and the universal second-order class $\Pi^1_1$ define different classes of properties over finite structures? (3) Is $P \ne NP \cap coNP$ — equivalently, is $P$ a proper subclass of $\Delta^1_1$ over finite structures? A complete answer settles all three questions; note that $P = NP$ implies equality throughout the chain, while a proof that $P \ne NP \cap coNP$ implies $P \ne NP$ without by itself settling $NP$ versus $coNP$.

References

1. Erin Carmody, "Nondeterministic infinite time Turing machines", arXiv:2312.15748 (2023), https://arxiv.org/abs/2312.15748
2. Ronald Fagin, "Generalized first-order spectra and polynomial-time recognizable sets", in Complexity of Computation, Proc. Symposium in Applied Mathematics (SIAM-AMS), New York City 1973, 43–73 (1974); zbMATH Zbl 0303.68035, https://zbmath.org/3474957
3. Leonid Libkin, "Elements of Finite Model Theory", Springer (2004). DOI 10.1007/978-3-662-07003-1, ISBN 978-3-662-07003-1, https://doi.org/10.1007/978-3-662-07003-1
4. Lance Fortnow, "The status of the P versus NP problem", Communications of the ACM 52(9):78–86 (2009). DOI 10.1145/1562164.1562186, https://doi.org/10.1145/1562164.1562186
5. Lance Fortnow, "Fifty years of P vs. NP and the possibility of the impossible", Communications of the ACM 65(1):76–85 (2022, January issue; published online December 2021). DOI 10.1145/3460351, https://doi.org/10.1145/3460351
6. Ralf Schindler, "P ≠ NP for Infinite Time Turing Machines", Monatshefte für Mathematik 139(4):335–340 (2003). DOI 10.1007/s00605-002-0545-5, https://doi.org/10.1007/s00605-002-0545-5
7. Vinay Deolalikar, Joel David Hamkins, Ralf Schindler, "P ≠ NP ∩ co-NP for Infinite Time Turing Machines", Journal of Logic and Computation 15(5):577–592 (2005). DOI 10.1093/logcom/exi022, https://doi.org/10.1093/logcom/exi022
8. Joel David Hamkins, Andy Lewis, "Infinite time Turing machines", Journal of Symbolic Logic 65(2):567–604 (2000). DOI 10.2307/2586556, https://doi.org/10.2307/2586556
9. Clay Mathematics Institute, "P vs NP" (Millennium Prize Problem page, listed as unsolved; accessed 2026-08-28), https://www.claymath.org/millennium/p-vs-np/