we-solve (beta)

CS-10 · computer science · mathematics · Computational complexity

P versus NP ∩ coNP

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

A language lies in $\mathsf{NP}\cap\mathsf{coNP}$ when both membership and nonmembership have polynomial-length certificates verifiable in deterministic polynomial time. Thus there are verifiers $V_1,V_0$ and polynomial length bounds satisfying \[ x\in L\iff\exists y\,V_1(x,y)=1,\qquad x\notin L\iff\exists z\,V_0(x,z)=1. \] Determine whether every such language belongs to $\mathsf P$, that is, $\mathsf P=\mathsf{NP}\cap\mathsf{coNP}$. Algorithms are uniform and unrelativized, and inputs are total languages rather than promise problems.

Formulation and concept references: [S1].

Short English statement

When both answers have efficiently checkable certificates, must the answer itself be efficiently computable?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 2

CS-10-A2 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-10

P versus NP ∩ coNP

Definitions and mathematical statement

A language lies in $\mathsf{NP}\cap\mathsf{coNP}$ when both membership and nonmembership have polynomial-length certificates verifiable in deterministic polynomial time. Thus there are verifiers $V_1,V_0$ and polynomial length bounds satisfying \[ x\in L\iff\exists y\,V_1(x,y)=1,\qquad x\notin L\iff\exists z\,V_0(x,z)=1. \] Determine whether every such language belongs to $\mathsf P$, that is, $\mathsf P=\mathsf{NP}\cap\mathsf{coNP}$. Algorithms are uniform and unrelativized, and inputs are total languages rather than promise problems.

Formulation and concept references: [S1].

Short English statement

When both answers have efficiently checkable certificates, must the answer itself be efficiently computable?

Research attempt

Scope, source check, and method.
This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. It examines the gap between verifying either answer and finding the answer, using an explicit total factor-threshold language and a careful analysis of certificate search. The two verifiers in the definition belong to a fixed language; their correctness and coverage hold on every input. No advice, oracle, or unmentioned promise is introduced.

Aaronson's lecture [S1] gives the class-comparison context. The recent permutation paper [S3] explicitly obtains separations relative to random permutations and related randomness notions. These do not constitute the unrelativized separation requested here. The only substantial external algorithm used in the concrete certificate construction below is the deterministic polynomial-time primality test of Agrawal--Kayal--Saxena [E1]. That theorem recognizes prime numbers; it does not output their factors. All reductions and certificate bookkeeping used here are proved explicitly.

The easy containment $\mathsf P\subseteq\mathsf{NP}\cap\mathsf{coNP}$ uses the deterministic decider itself as a verifier for each answer, with an empty witness. To prove strict containment one needs a total language having both certificate types but no deterministic polynomial-time decider. To prove equality one needs a uniform decider for every fixed pair of correct two-sided certificate relations. Neither task is accomplished by exhibiting an interesting pair of verifiers alone.

Attack A: a fully total decision version of factoring.
Fix a standard, efficiently parsed binary encoding of pairs of nonnegative integers. Define \begin{equation}\label{wsref-0-61-33-34-3a-66-61-63-74-6f-72-6c-61-6e-67-75-61-67-65} F=\{\langle N,K\rangle:N\ge2,\ \exists d\in\mathbb Z, \ 2\le d<N,\ d\le K,\ d\mid N\}. \end{equation} Malformed strings and pairs with $N<2$ are not in $F$. No promise of compositeness, semiprimality, or a restricted threshold is imposed. The bit length of a valid input is comparable to the sum of the bit lengths of $N$ and $K$, and polynomial means polynomial in that length.
Lemma 34.1: both answers have short certificates.
The language $F$ belongs to $\mathsf{NP}\cap\mathsf{coNP}$.

Yes-certificates. A witness is the divisor $d$. Verify the bounds $2\le d<N$, $d\le K$, and compute $N\bmod d$. Its length is at most $O(\log(N+2))$, and ordinary integer arithmetic verifies it in polynomial time. No claim that $d$ itself is prime is needed.

No-certificates. Malformed inputs, $N<2$, and $K<2$ can be recognized and rejected by the language decider immediately, so their nonmembership certificates are a fixed tag. In the remaining cases provide a list of primes, repeated with multiplicity, \[ p_1,\ldots,p_t,\qquad N=\prod_{i=1}^t p_i. \] Check the product exactly and check primality of each entry using [E1]. The no-verifier then accepts if either $t=1$ or every $p_i>K$. The product condition with prime entries implies $t\le\log_2 N$, and the list has polynomial encoded length, for example $O((\log(N+2))^2)$ with simple delimiters.

If $t=1$, $N$ is prime and has no proper divisor. If $t\ge2$, every prime factor is proper. A divisor $d\ge2$ of $N$ contains a prime factor $p_i$ with $p_i\le d$. Thus all prime factors being greater than $K$ precludes an allowed divisor. Conversely, if $N$ is composite and has no allowed divisor, none of its prime factors can be at most $K$; its complete prime factorization is therefore an accepted no-certificate. This proves soundness and completeness for both sides, including $K\ge N$ and prime $N$. $\square$

The distinction between existence and discovery is visible here. A complete factorization can be checked quickly even though no deterministic polynomial-time construction of such a list is supplied. The no-verifier must verify that the supplied prime factors multiply to all of $N$; an incomplete list would not rule out a smaller omitted factor.

Lemma 34.2: deciding this language is equivalent to factoring.
The following are equivalent: $F\in\mathsf P$, and there is a deterministic polynomial-time algorithm outputting a complete prime factorization of every binary integer $N\ge2$.

Proof, decision to factorization. Given $N$, query $F$ at $(N,N-1)$. A no answer says $N$ is prime. A yes answer says it is composite, and the predicate $K\mapsto\mathbf1_F(N,K)$ is monotone. Binary search on $2\le K\le N-1$ finds its smallest true threshold using $O(\log N)$ queries. That threshold is the smallest prime factor: the smallest proper divisor cannot be composite, since a prime divisor of it would be a smaller proper divisor of $N$. Output this prime, replace $N$ by its quotient, and repeat until the quotient is one or is declared prime.

Every removal divides the current integer by at least two. There are at most $\log_2 N$ removals, and every query has $O(\log N)$ bits. Thus $O((\log N)^2)$ calls to a polynomial-time decider, together with polynomial integer arithmetic, suffice. The search uses binary thresholds and never loops through $N$ candidate integers.

Proof, factorization to decision. First reject malformed or out-of-range inputs. Factor $N$. If the list has one prime entry, answer no. Otherwise compare the smallest prime factor with $K$. The equivalence established in Lemma 34.1 proves this decides (a34:factorlanguage). Polynomial time is measured in the binary input length in both directions. $\square$

Consequently equality of the two classes in the target would imply deterministic polynomial-time factoring. A proof that this particular total language is outside P would give a negative answer to the target. Neither a lack of a known factoring algorithm nor success of quantum factoring is such a classical lower bound. Conversely, a classical factoring algorithm would settle this candidate language but would not establish the class equality for all two-sided certificate relations.

Attack B: convert two certificates into a total search task.
Pad the witness bounds to a common polynomial $p(n)$, using an explicit length field if necessary. Define the polynomially checkable relation \[ R(x,b,w)\quad\Longleftrightarrow\quad b\in\{0,1\},\quad |w|\le p(|x|),\quad V_b(x,w)=1. \] For every input $x$, some pair $(b,w)$ satisfies $R$, and all satisfying pairs have the same bit $b=1_L(x)$. A polynomial-time algorithm finding any such pair would decide $L$. This gives a sufficient search route, but totality alone does not supply the search algorithm.

Exhaustive search through both types of witness does terminate, with an upper bound exponential in the polynomial witness length. If either side has witnesses of length at most $c\log(n+2)$, exhaustive search on that side alone is polynomial and decides the language: acceptance of one witness gives that side's answer, and absence of all witnesses gives the other. For a general polynomial bound $p(n)$, the same enumeration has $2^{\Theta(p(n))}$ candidates and proves no polynomial runtime.

The prefix-extension gap in search-to-decision.
A natural strategy is to ask whether a desired witness can begin with a given prefix. For yes-certificates this predicate is \[ S=\{(x,u):\exists w\text{ extending }u,\ |w|\le p(|x|),\ V_1(x,w)=1\}. \] It is in NP. However a no answer need not be certified by $V_0$: there may be a valid yes-certificate for $x$ beginning with another prefix. For an explicit example take the trivial language of all strings and let $V_1(x,w)$ accept exactly when $w=0^{|x|}$, while $V_0$ always rejects. For $|x|\ge1$ the prefix $1$ has no extension, although no $V_0$ certificate exists. Thus the proposed complement verifier fails on a concrete input. This does not prove that $S$ is outside coNP; it proves that the original pair of verifiers does not automatically certify prefix nonextendibility.

Accordingly, even assuming the equality asked in this problem would not justify invoking it on every NP prefix predicate. Under the stronger assumption $\mathsf P=\mathsf{NP}$, those queries could be answered and ordinary prefix search would work. Importing that stronger assumption here would change the problem.

Why finding the presented witness can be a stronger demand.
Let $T(x,w)$ be any polynomial-time decidable, polynomially balanced relation with at least one witness for every input. These are the total NP search relations commonly grouped under TFNP [E2]. Set $L=\{0,1\}^*$, let $V_1(x,w)=T(x,w)$, and let $V_0$ always reject. This is a valid two-sided certificate description of a language already in P. Yet finding a witness for this particular $V_1$ is exactly the original total search problem. Therefore a method that efficiently finds witnesses for every supplied valid verifier pair would solve all such total search problems, even for constant-answer languages. The class-equality question only asks to decide the answer; it does not demand efficient search for arbitrary presented certificate systems. This construction identifies the additional obligation in the proposed search route, without asserting a separation for TFNP.

There is a related promise trap in making the verifier pair itself part of the input. Arbitrary pairs of polynomial-time programs need not be sound, disjoint, or collectively total. Two always-rejecting verifiers leave every input uncovered; two always-accepting verifiers certify both answers. A universal problem restricted to well-behaved pairs therefore has a semantic promise unless one supplies a separate, sound way to enforce that condition. No total-language completeness result is obtained merely by writing down such program pairs.

Verification, remaining gap, and outcome.
The companion exact checks compare the factor-threshold predicate with the prime-factor certificate criterion over small integers and every relevant threshold, including primes, squares, repeated factors, and thresholds outside $[2,N-1]$. They then implement the binary-search reduction and recover the complete factorizations in those cases. Small examples also test the prefix obstruction. Trial division is used only inside this finite verification script; the polynomial verifier in Lemma 34.1 invokes the established primality theorem, not trial division on binary integers.

UNRESOLVED. The concrete progress is a total language with fully specified certificates on both sides and a proved deterministic equivalence to factoring. The general search route has exact missing steps: totality is not a polynomial search procedure, the complement of a prefix predicate is not supplied by the opposite-answer verifier, and arbitrary verifier pairs need not define total languages. A solution still requires either one unconditional lower bound for a genuine two-sided-certificate language, or a uniform decision method for every such language. No such bound or method is established, and no novelty is claimed for the standard reductions or elementary counterexamples.

Sources

Go to contribution →

CS-10-A1 · No claim recorded · LLM-generated · gpt 6 astra pro ·

gpt 6 astra pro attempt on CS-10

P versus NP ∩ coNP

Definitions and mathematical statement

A language lies in $\mathsf{NP}\cap\mathsf{coNP}$ when both membership and nonmembership have polynomial-length certificates verifiable in deterministic polynomial time. Thus there are verifiers $V_1,V_0$ and polynomial length bounds satisfying \[ x\in L\iff\exists y\,V_1(x,y)=1,\qquad x\notin L\iff\exists z\,V_0(x,z)=1. \] Determine whether every such language belongs to $\mathsf P$, that is, $\mathsf P=\mathsf{NP}\cap\mathsf{coNP}$. Algorithms are uniform and unrelativized, and inputs are total languages rather than promise problems.

Formulation and concept references: [S1].

Short English statement

When both answers have efficiently checkable certificates, must the answer itself be efficiently computable?

Research attempt

Current frontier.
The language-class question is exactly the dual-certification question in Aaronson's lecture, not a promise or search-class comparison. [S1]. Hitchcock--Sekoni--Shafei obtain the corresponding separation relative to individually random permutation oracles; their Theorem 5.1 does not construct an ordinary polynomial-time permutation with a hard inverse. [S3], [E1]. Recent work on total randomized search separates several black-box models and gives conditional white-box consequences, but it does not turn totality into deterministic polynomial-time search. [E2]. The literature points to two distinct obstacles: certificates may be difficult to locate, and an oracle carrying the desired hard data is not an effective construction of those data. The recent theorem statements were inspected, not independently proof-audited in full.
Attack route.
For a negative answer, a natural target is a uniquely determined object whose bits are efficiently certifiable in both directions, such as the inverse of a polynomial-time permutation. For a positive answer, one could try to combine the two certificate families into an efficient search. I pursue the common interface between these routes: unique outputs versus unique certificates, and the complexity of selecting a certificate consistent with partial information. These distinctions are essential to avoid assuming the answer in a canonicalization step.
Attempt.
Call a relation $R(x,y,z)$ a total single-output verification scheme if it is deterministic polynomial-time decidable, the lengths of $y,z$ are bounded by fixed polynomials in $|x|$, and for every $x$ there is exactly one string $y=f(x)$ for which some $z$ satisfies $R(x,y,z)$. Pad the output to a fixed polynomial length, with an encoded original length if necessary. There may be many valid $z$ for this one $y$.

Lemma 34.1 (an exact output-search formulation). The equality $\mathsf P=\mathsf{NP}\cap\mathsf{coNP}$ holds if and only if every total single-output verification scheme has its output function in $\mathsf{FP}$.

Proof. Given such a scheme, let \[ B=\{\langle x,i\rangle:1\le i\le\ell(x),\ f(x)_i=1\}. \] On a valid input, a certificate for membership guesses $y,z$ with $R(x,y,z)$ and $y_i=1$; a certificate for nonmembership guesses a valid output with $y_i=0$. Uniqueness and totality prove both soundness and completeness. Malformed inputs are rejected deterministically and so also have a polynomial-time complementary verifier. Thus $B\in\mathsf{NP}\cap\mathsf{coNP}$. Under the stated equality, deciding its polynomially many bits computes $f$ in polynomial time.

Conversely, for $L\in\mathsf{NP}\cap\mathsf{coNP}$ with verifiers $V_1,V_0$, let $R(x,b,z)=V_b(x,z)$ for the one-bit output $b\in\{0,1\}$. Exactly one value of $b$ has a certificate. An output algorithm for this scheme decides $L$. This proves the equivalence with all quantifiers over fixed uniform verifiers and fixed polynomial bounds intact.$\square$

The lemma identifies the requisite search power, but does not establish it. For an arbitrary total polynomial-time relation, independently choosing each bit that appears in some solution is invalid. With solution set $\{01,10\}$ the existential bit answers are $11$, not a solution. Sequential prefix extension repairs this consistency problem, but introduces the predicate \begin{equation}\label{wsref-0-72-33-34-3a-70-72-65-66-69-78} E(x,u)\quad\Longleftrightarrow\quad \exists y,z\,[R(x,y,z)\ \text{and }u\text{ is a prefix of }y]. \end{equation} For multiple possible outputs, nonextendibility does not in general have a certificate obtained just by displaying another solution. For a unique output, a conflicting output does certify nonextendibility, so $E$ is again in $\mathsf{NP}\cap\mathsf{coNP}$. This recovers the same unresolved decision problem rather than eliminating it.

Trying to force a canonical certificate. One might replace a verifier $V(x,w)$ by its lexicographically least valid witness. Correct verification would then require \[ V(x,w)=1\quad\text{and}\quad \forall w'<w,\ V(x,w')=0. \] The second condition is universal. A polynomial-time verification algorithm for it has not been furnished merely by the existence of dual certificates for $x$. Even when $x$ is known to be a yes-instance, its no-verifier need not certify that a subcollection of yes-certificates is empty. The following elementary decision-tree comparison makes the algorithmic cost of this missing operation explicit.

Lemma 34.2 (what a certificate-elimination argument actually uses). Let $f:\{0,1\}^n\to\{0,1\}$ be total. A bit certificate is a partial assignment forcing an output. Suppose the largest minimum zero-certificate size is $c_0$ and the analogous one-size is $c_1$. Then a deterministic decision tree of depth at most $c_0c_1$ exists. This bound does not charge for finding the certificates defining the tree.

Proof. If $f$ is constant, no queries are needed. Otherwise choose a one-input and a one-certificate for it of size at most $c_1$, and query those positions. If every value matches, output one. On each other branch, consider a zero-input still consistent with the answers and one of its zero-certificates of size at most $c_0$. That certificate must conflict with the chosen one-certificate: otherwise a common completion would force both outputs. At least one of its positions has now been queried. Deleting the queried positions leaves a zero-certificate of size at most $c_0-1$ for the restricted function. Its one-certificate complexity is at most $c_1$. Induction proves the depth bound; if one output type disappears, the branch is constant.$\square$

This attractive bound does not solve the Turing-machine problem. Selecting a consistent one-input can be difficult even when evaluating $f$ is easy. Given a Boolean circuit $C$ and a partial assignment $u$, the task of finding any $a$ extending $u$ with $C(a)=1$, or correctly reporting none, decides CircuitSAT by taking $u$ empty. In contrast, evaluating $C(a)$ on a given $a$ is polynomial time. Thus the decision-tree construction can hide an NP-hard selection subroutine inside an argument about an easy decision function. Moreover arbitrary NP certificates are not necessarily partial assignments of input bits. Both mismatches must be repaired, not suppressed. The CircuitSAT formulation is given in [S1].

Testing the negative route. Let $p_n$ be any uniformly polynomial-time bijection of $\{0,1\}^n$. The language \[ L_p=\{\langle1^n,y,i\rangle:(p_n^{-1}(y))_i=1\} \] uses the inverse $x$ as a certificate for either bit. It lies even in $\mathsf{UP}\cap\mathsf{coUP}$, because $x$ is unique. If $L_p$ has a deterministic polynomial-time algorithm, then $n$ bit queries invert $p_n$ on every input. Conversely a polynomial-time inverse decides $L_p$. Therefore an explicit polynomial-time permutation without a polynomial-time inverse would separate the classes in this entry. Average-case one-wayness, as in UnsolvedMath problem 30006696, is more than this deduction needs; worst-case inverse hardness suffices. No such unconditional hardness is proved here. The oracle construction in [E1] cannot replace it, since its forward permutation is supplied as an oracle rather than a uniform algorithm.

Stress test.
Lemma 34.1 permits many auxiliary certificates for one output, so it does not silently replace $\mathsf{NP}\cap\mathsf{coNP}$ by its unambiguous subclass. Uniqueness concerns the entire output, not merely each separately selected bit. Totality is indispensable to the complementary bit verifier; for a partial function, an outputless input has neither bit certificate. Constant functions and malformed encodings have been treated explicitly.

The accompanying script checks the inequality $D(f)\le C_0(f)C_1(f)$ for all Boolean functions of three variables, computing optimal decision-tree depth by recursion on partial assignments. It also checks the two-witness bit-selection failure. These finite checks say nothing about the uniform cost of constructing trees as the input length grows. A proof of separation here would imply $\mathsf P\ne\mathsf{NP}$; the exact-output equivalence cannot be used to obtain that implication without supplying the missing hard function.

\Needspace{8\baselineskip}

Outcome.
Outcome: Exploratory approach with unresolved gap.

The attempt isolates an exact single-output search reformulation and verifies why two tempting positive strategies fail: independent witness-bit choice can be inconsistent, and canonical or decision-tree certificate selection can conceal a harder problem than the original decision task. The negative route is reduced to an explicit worst-case-hard permutation inverse, but no such construction is established. These are proved structural deductions, not a new class separation or a claim of historical novelty.

Sources

Go to contribution →