P versus NP Problem

P vs. NP

Definitions and mathematical statement

A decision problem is a language $L\subseteq\{0,1\}^*$ of finite binary strings. Its input size is the string length $|x|$. The class $\mathrm P$ consists of languages decided by a deterministic Turing machine in at most $C(|x|+1)^c$ steps for some fixed constants $C,c$. The machine must halt and answer correctly on every input.

A language belongs to $\mathrm{NP}$ if there are a polynomial $p$ and a deterministic polynomial-time predicate $V$ such that \[ x\in L\quad\Longleftrightarrow\quad \exists y\in\{0,1\}^{\le p(|x|)}\quad V(x,y)=1. \] The string $y$ is a certificate for a yes-instance. Its length and the verification time are bounded by fixed polynomials, uniformly over all inputs. The problem is to decide whether $\mathrm P=\mathrm{NP}$. Since $\mathrm P\subseteq\mathrm{NP}$, inequality means exhibiting a language in $\mathrm{NP}$ with no deterministic polynomial-time decision procedure.

The question uses the ordinary uniform, worst-case bit model of computation. It does not permit a separate uncomputable advice string for each input size or replacement by a quantum algorithm. Efficient verification for no-instances is not part of the definition of $\mathrm{NP}$. Polynomial-time solution of every input, rather than success on a selected distribution of inputs, is required.

Short English statement

Does every decision problem with efficiently checkable yes-certificates also admit an efficient deterministic decision algorithm?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3395 (OPG-661), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, P vs. NP. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/p_vs_np.

Research attempt

The target is the ordinary uniform worst-case question $\mathrm P=\mathrm{NP}$. This attempt tests a possible lower-bound route: split inputs into two blocks, build a truth-value matrix, and infer a large circuit from exponential matrix rank. The inference fails even on a language with a uniform linear-time algorithm. Establishing that failure does not separate $\mathrm P$ from $\mathrm{NP}$.

For $n\ge1$ define $\operatorname{EQ}_n(x,y)=1$ if $x=y$ and zero otherwise, for $x,y\in\{0,1\}^n$. Let $M_n$ be its $2^n$-by-$2^n$ matrix, with rows indexed by $x$, columns by $y$, in the same order, over the real field.

What the rank actually lower-bounds.

If a function has a representation $f(x,y)=\sum_{j=1}^r a_j(x)b_j(y)$ over the reals, its matrix has rank at most $r$, because each summand has all columns proportional to one vector and the total column space lies in the span of the $r$ vectors $a_j$. Conversely, if a matrix has rank $r$, choose $r$ basis columns; expressing every column in that basis yields exactly such a sum of $r$ outer products. Therefore matrix rank is precisely a lower bound on this separable-sum representation. It is not a lower bound of comparable magnitude on arbitrary Boolean circuits. The equality circuit combines simple cross-block tests with products; expanding those products into a separable sum can create exponentially many terms.

For contrast, a deterministic one-way communication protocol in which Alice knows $x$, Bob knows $y$, and Alice sends a fixed-length message must send at least $n$ bits for exact equality. If two different $x,x'$ induce the same message, Bob on $y=x$ receives the same information for the accepting pair $(x,x)$ and rejecting pair $(x',x)$, a contradiction. Thus there must be at least $2^n$ messages. This proof identifies another genuinely restricted model. It supplies only a linear communication bound, consistent with the linear circuit, and no superpolynomial time lower bound.

Literature and context

The source's Open Problem Garden identity is preserved and is a repeated formulation of the classical problem, not a new independent conjecture. Clay Mathematics Institute's official P-versus-NP page was inspected on 11 October 2026 and continues to present the problem as unsolved. That page is used for current context, not as mathematical evidence for either answer. The rank calculation and circuit construction above are elementary and not claimed novel. No comprehensive survey of circuit lower-bound barriers or novelty check on rank methods was completed.

Verification and remaining gaps

The script constructed identity matrices for $n=1,\ldots,8$ and numerically recovered ranks $2,4,\ldots,256$. The algebraic proof already establishes every $n$; these matrix checks are diagnostic only. The gate count was checked at $n=1$, where no final combining gate is needed. The audit separated a uniform machine from circuit families and identified exactly which restricted representation matrix rank controls. To repair this route one would need an invariant that remains bounded for every polynomial-time computation yet grows superpolynomially for a particular NP language; no such invariant or argument is supplied. A large rank alone cannot be that invariant because equality is a counterexample.

References

Original S1--S2 above. Clay Mathematics Institute, P vs NP, official problem page, https://www.claymath.org/millennium/p-vs-np/, inspected 11 October 2026. All rank, circuit and communication claims used in the failed-route audit are proved here; no external lower-bound theorem is invoked.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch and contributed formatting/repository review. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch001/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.

P versus NP Problem

Definitions and mathematical statement

A language is a set $L\subseteq\{0,1\}^*$. Write $\mathsf P$ for languages decided by a deterministic Turing machine in time bounded by a polynomial in the input length. A language belongs to $\mathsf{NP}$ if there are a deterministic polynomial-time verifier $V$ and a polynomial $p$ such that \[ x\in L\quad\Longleftrightarrow\quad \exists y\in\{0,1\}^{\le p(|x|)}\;V(x,y)=1. \] The polynomial and machine may depend on $L$, but not on its individual inputs. The question is whether $\mathsf P=\mathsf{NP}$. A negative answer requires a language in $\mathsf{NP}$ outside $\mathsf P$, not merely a slow algorithm for one problem.

Formulation and concept references: [S1], [E1].

Short English statement

Does an efficient way to check a proposed yes-answer always imply an efficient way to decide whether the answer is yes?

Sources

• S1 Clay Mathematics Institute, The Millennium Prize Problems. https://www.claymath.org/library/monographs/MPPc.pdf. Catalogue formulation source.
• S2 P vs NP. https://www.claymath.org/millennium/p-vs-np/. Catalogue research/status reference; not a proof endorsement.
• S3 Constructive solvability and the P versus NP problem — Arne Hole. https://arxiv.org/abs/2406.16843. Catalogue research/status reference; not a proof endorsement.
• S4 PNP Labs — P versus NP formal reconstruction. https://pnplabs.com.au/. Catalogue research/status reference; not a proof endorsement.
• E1 Stephen Cook, The P versus NP Problem, Clay Mathematics Institute, Section 1 and Appendix. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf. Added primary source: Definitions and formulation. Consulted 24 September 2026.

• E2 Theodore Baker, John Gill and Robert Solovay, Relativizations of the $\mathcal P=?\mathcal{NP}$ Question, SIAM Journal on Computing 4$4$ $1975$, 431--442, oracle equality and separation results. https://doi.org/10.1137/0204037. Consulted 24 September 2026: publisher abstract; used only for the stated oracle obstruction, not a new proof audit.
• E3 Alexander A. Razborov and Steven Rudich, Natural Proofs, Journal of Computer and System Sciences 55$1$ $1997$, 24--35; author manuscript dated 30 November 1996, abstract and the natural-property/hardness framework. https://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf. Consulted 24 September 2026. The pseudorandomness assumption is retained; no unconditional barrier is asserted.
• E4 Scott Aaronson and Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory 1$1$ $2009$, Article 2; author manuscript, Sections 1--2 and 5, especially Theorems 5.1 and 5.3. https://www.scottaaronson.com/papers/alg.pdf. Consulted 24 September 2026: definitions and barrier statements.
• E5 Ryan Williams, Nonuniform ACC Circuit Lower Bounds, Journal of the ACM 61$1$ $2014$, Article 2, 32 pages; author manuscript, Theorem 1.1 and Section 1.1. https://people.csail.mit.edu/rrw/acc-lbs.pdf. https://doi.org/10.1145/2559903. Consulted 24 September 2026.
• E6 Lijie Chen, Avishay Tal and Yichuan Wang, Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits, ECCC TR26-039, 15 March 2026, abstract and reported $\mathsf E^{\mathsf{NP}}$ threshold-circuit bound. https://eccc.weizmann.ac.il/report/2026/039/. Consulted 24 September 2026: report page and abstract. A recent manuscript result, not an independent verification of its full proof.
• E7 Adnan Darwiche and Pierre Marquis, A Knowledge Compilation Map, Journal of Artificial Intelligence Research 17 $2002$, 229--264, Sections 1--2 and the separation of succinctness, queries and transformations. https://arxiv.org/abs/1106.1819. https://doi.org/10.1613/jair.989. Consulted 24 September 2026: article introduction and language definitions. Used as methodological context, not as the source of Lemma 1.1.

P versus NP Problem

Definitions and mathematical statement

A language is a set $L\subseteq\{0,1\}^*$. Write $\mathsf P$ for languages decided by a deterministic Turing machine in time bounded by a polynomial in the input length. A language belongs to $\mathsf{NP}$ if there are a deterministic polynomial-time verifier $V$ and a polynomial $p$ such that \[ x\in L\quad\Longleftrightarrow\quad \exists y\in\{0,1\}^{\le p(|x|)}\;V(x,y)=1. \] The polynomial and machine may depend on $L$, but not on its individual inputs. The question is whether $\mathsf P=\mathsf{NP}$. A negative answer requires a language in $\mathsf{NP}$ outside $\mathsf P$, not merely a slow algorithm for one problem.

Formulation and concept references: [S1], [E1].

Short English statement

Does an efficient way to check a proposed yes-answer always imply an efficient way to decide whether the answer is yes?

Research attempt

Current frontier and source audit.

The target here is the ordinary, uniform, classical language-class question. Cook's NP-completeness theorem makes a deterministic polynomial-time algorithm for Boolean circuit satisfiability sufficient for equality; a lower bound for one restricted representation of satisfying assignments is not sufficient for inequality [E1]. An established milestone on the lower-bound side is Williams's nonuniform ACC lower bound for nondeterministic exponential time, not a lower bound for arbitrary circuits computing an NP language [E5]. As a recent, model-specific result, the March 2026 manuscript of Chen, Tal and Wang reports $n^{5/2-\varepsilon}$ gate lower bounds against depth-two threshold circuits for a function in $\mathsf E^{\mathsf{NP}}$ [E6]. The class, gate basis and quantifiers in that statement cannot be replaced by those of this problem. These are relevant checkpoints, not a claim that one numerical bound describes the entire frontier.

Three obstructions must be kept separate. Baker--Gill--Solovay construct oracle worlds with opposite answers; hence an argument valid unchanged for every oracle cannot settle this question [E2]. The natural-proofs obstruction is conditional on sufficiently strong pseudorandomness and concerns its specific constructivity, largeness and usefulness requirements; it is not an unconditional prohibition on combinatorial lower bounds [E3]. Aaronson--Wigderson's algebraic-oracle results show why merely replacing Boolean queries by low-degree extensions does not supply a general escape [E4]. None of these results says that an explicit, syntax-sensitive argument is impossible.

The existing catalogue claims were also checked for scope. The abstract of Hole's September 2026 version explicitly uses a finiteness condition and a constructive interpretation [S3]. Under the present definition, however, $\mathsf{NP}\subseteq\mathsf{EXPTIME}$ follows directly: on input length $n$, try all fewer than $2^{p(n)+1}$ permitted witnesses and run the fixed verifier on each. This argument does not require a theory that proves an algorithm correct. Thus an assertion about unprovability of algorithmic correctness is not by itself a separation of these language classes. The PNP Labs page contains self-reported formalized components together with explicitly unproved global and polynomial-runtime endpoints [S4]; those components are not used as a theorem settling the target.

Attack map and selected route.

A diagonalization route would have to diagonalize against every polynomial exponent while retaining one polynomially bounded NP verifier. Simulating the $i$th machine for $n^i$ steps does not accomplish that: the exponent then varies with the input. A circuit route would need a superpolynomial lower bound for an NP language against unrestricted circuits; obtaining that would additionally settle Section 30006678 negatively, a stronger conclusion than is requested here. An upper-bound route can instead exploit the explicit gate syntax of a verifier and try to eliminate existential variables while retaining a compact exact description of the remaining feasible set. The last route is pursued below. Its precise missing ingredient is a uniformly computable, polynomial-size summary preserved through all the required eliminations, not merely a succinct input formula. The distinction between succinctness, tractable queries and tractable transformations is central in knowledge compilation [E7].

The proposed combination is linear algebra over ${\mathbb{F}}_2$, affine summaries of nonlinear gates, and decomposition into independent factors. The reasoning below was developed for this notebook. The elementary lemmas are proved here; no claim of historical novelty or of a new general complexity lower bound is made.

Attempt: an exact algebraic encoding.

For a circuit with AND, OR and NOT gates, introduce a variable for every input and every gate output. Over ${\mathbb{F}}_2$, impose, respectively, \begin{equation}\label{wsref-0-72-61-3a-31-3a-67-61-74-65-73} z+xy=0,\qquad z+x+y+xy=0,\qquad z+1+x=0, \end{equation} and impose $z_{\rm out}=1$. All variables range over ${\mathbb{F}}_2$; no relaxation to arbitrary field extensions is being made. Induction in a topological ordering of the circuit proves that every input has exactly one extension to its gate values, and that this extension satisfies the output equation exactly when the circuit accepts. There are polynomially many variables and quadratic equations in the circuit's bit length. Conversely, a proposed solution of such a system is polynomially checkable. Consequently a uniform polynomial-time solver for all these quadratic systems would decide circuit satisfiability and hence give $\mathsf P=\mathsf{NP}$ [E1].

Gaussian elimination solves affine systems and computes coordinate projections of affine subspaces. This suggests storing a feasible relation as a union of affine subspaces, and using linear algebra on each piece. The following sharp calculation tests how much such a representation can compress even a quadratic graph.

Lemma 1.1 (exact affine-cover size of a quadratic graph). Let $Q:{\mathbb{F}}_2^d\to{\mathbb{F}}_2^m$ have coordinate polynomials of degree at most two, in multilinear form, and define its vector-valued polar form by \[ B(u,v)=Q(u+v)+Q(u)+Q(v)+Q(0). \] This is alternating and bilinear. Put \[ \alpha(B)=\max\{\dim U:U\le{\mathbb{F}}_2^d,\ B(u,v)=0\text{ for all }u,v\in U\}, \qquad \Gamma_Q=\{(x,Q(x)):x\in{\mathbb{F}}_2^d\}. \] If $\kappa(\Gamma_Q)$ is the least number of affine subspaces whose union is exactly $\Gamma_Q$, then \begin{equation}\label{wsref-0-72-61-3a-31-3a-63-6f-76-65-72} \kappa(\Gamma_Q)=2^{d-\alpha(B)}. \end{equation} The same minimum holds when each piece may instead be the coordinate projection of an affine subspace with any number of auxiliary variables.

Proof. Let $A\subseteq\Gamma_Q$ be an affine subspace. Projection onto the input coordinates is injective on $A$, since a graph has only one output per input. Its image is an affine space $x_0+U$ of dimension $\dim A$. The restriction of $Q$ to that space is affine. Its second additive difference is therefore zero: \[ Q(x_0)+Q(x_0+u)+Q(x_0+v)+Q(x_0+u+v)=B(u,v)=0 \quad(u,v\in U). \] Thus $\dim A\le\alpha(B)$ and $|A|\le2^{\alpha(B)}$. Since the graph has $2^d$ points, any exact cover has at least $2^{d-\alpha(B)}$ pieces, even with overlap.

For the reverse bound, choose a totally isotropic $U$ of maximum dimension. On every coset $x_0+U$, the map \[ u\longmapsto Q(x_0+u)+Q(x_0) \] is additive by the displayed second-difference identity, and hence linear over ${\mathbb{F}}_2$. The graph above that coset is an affine space. The $2^{d-\alpha(B)}$ cosets partition the input space and their graphs partition $\Gamma_Q$. Finally a coordinate projection of an affine subspace is itself affine. An exact union cannot contain a piece with a point outside the graph, so auxiliary affine variables cannot evade the same lower bound.$\square$

Corollary 1.2 (a constructive special-case solver). Given $Q$, $b\in{\mathbb{F}}_2^m$, and an explicitly supplied basis of a totally isotropic subspace $U$ of dimension $r$, solvability of $Q(x)=b$ can be decided in \begin{equation}\label{wsref-0-72-61-3a-31-3a-61-6c-67-6f-72-69-74-68-6d} 2^{d-r}\operatorname{poly}(d,m) \end{equation} bit operations, with polynomial working space when solutions need not all be stored. Indeed extend the basis of $U$ to a basis of ${\mathbb{F}}_2^d$, enumerate the $2^{d-r}$ complementary representatives $x_0$, and solve the linear system \[ Q\!\left(x_0+\sum_{j=1}^r t_ju_j\right) =Q(x_0)+\sum_{j=1}^r t_j\left(Q(x_0+u_j)+Q(x_0)\right)=b. \] All coefficients are bits. A polynomial bound for the displayed enumeration would follow from $d-r=O(\log N)$, where $N$ is the encoded input size, provided the required basis is also found in polynomial time. Neither the existence nor the efficient discovery of such a basis is assumed for a general circuit encoding. When the constraint system is a conjunction of independent systems on disjoint variable sets, the work is a sum of these costs over the components, not their product. This is the useful part of combining affine algebra with factorization.

Attempt: falsifying the proposed compression invariant.

Take \[ Q_n(x_1,y_1,\ldots,x_n,y_n)=(x_1y_1,\ldots,x_ny_n). \] For the $i$th coordinate of its polar form, \[ B_i(u,v)=u_{x_i}v_{y_i}+u_{y_i}v_{x_i}. \] If $U$ is totally isotropic, its projection onto each pair $(x_i,y_i)$ has dimension at most one: a two-dimensional projection contains two vectors with determinant one, contradicting isotropy. The combined coordinate projections are injective, so $\dim U\le n$. Equality is attained by $y_i=0$ for all $i$. Lemma 1.1 gives \begin{equation}\label{wsref-0-72-61-3a-31-3a-61-6e-64-63-6f-76-65-72} \kappa(\Gamma_{Q_n})=2^n. \end{equation} Nevertheless its graph is described by just $3n$ CNF clauses, \[ \bigwedge_{i=1}^n \left[(\neg z_i\vee x_i)\wedge(\neg z_i\vee y_i) \wedge(z_i\vee\neg x_i\vee\neg y_i)\right], \] with $O(n\log(n+1))$ bits in a standard variable-index encoding. The all-zero assignment satisfies it, and membership in the graph is checked in linear many Boolean operations. Even satisfiability after arbitrary variable restrictions is decided independently on the $n$ triples. Thus a universal polynomial bound on flat affine summaries is false on a plainly tractable family. The exact cover bound cannot be promoted to a lower bound for arbitrary SAT algorithms.

Factorization repairs this particular example: keep the $n$ ternary relations as independent factors rather than distributing their conjunction over all affine choices. But connectedness alone is not the missing invariant. The single scalar equation \[ q(x,y)=\sum_{i=1}^n x_i y_i=b \] involves every variable and has a nondegenerate symplectic polar form. If $U$ is isotropic, $U\subseteq U^\perp$ and $\dim U^\perp=2n-\dim U$, giving $\alpha(B)=n$. Its graph again needs $2^n$ affine pieces. Yet $b=0$ is solved by the zero vector and $b=1$ by $x_1=y_1=1$, all other coordinates zero. Large affine-cover complexity, even for a connected quadratic relation, need not imply decision hardness.

Attempt: can quadratic factors be retained through projection?

A second possible repair is to store a conjunction of quadratic equations, without flattening it, and eliminate internal variables while remaining in that language. There is already a finite obstruction. Eliminating $w$ from \[ w=xy,\qquad z=wt \] gives the four-variable relation \begin{equation}\label{wsref-0-72-61-3a-31-3a-63-75-62-69-63} R=\{(x,y,t,z):z=xyt\}. \end{equation} It cannot be defined by any conjunction of quadratic equations over ${\mathbb{F}}_2$ on these four visible variables alone.

To prove this, reduce every polynomial modulo $v^2-v$ in each variable; this does not increase degree or change its Boolean zero set. A quadratic polynomial vanishing on $R$ has the form \[ q_0(x,y,t)+z\ell(x,y,t),\qquad \deg q_0\le2,\quad\deg\ell\le1. \] For the seven triples different from $(1,1,1)$, the graph has $z=0$, so $q_0$ vanishes there. A Boolean function supported only at $(1,1,1)$ is either zero or $xyt$: the squarefree monomials form a basis of all functions on ${\mathbb{F}}_2^3$. As $q_0$ has degree at most two, it must be the zero function. Evaluating at the remaining graph point then gives $\ell(1,1,1)=0$. Consequently every quadratic vanishing on $R$ also vanishes at $(1,1,1,0)$, which is not in $R$. No number of such equations can cut out $R$. This disproves the proposed closure lemma, rather than merely failing to prove an efficient implementation.

Allowing degree three represents this example immediately; keeping $w$ as an existential variable also represents it. The former permits degree growth under repeated elimination, and the latter has not eliminated the search problem. Neither observation rules out more flexible algorithms, but neither closes the proposed upper bound.

Computational check.

The accompanying script research_batch01_checks.py enumerates every linear subspace of ${\mathbb{F}}_2^{2n}$ in reduced row-echelon form for $n=1,2,3$, checks isotropy on basis pairs, and independently forms the affine graph pieces over their cosets. The total subspace counts are $5,67,2825$; the maximum isotropic dimensions are $1,2,3$, with $3,9,27$ maximum-dimensional isotropic subspaces. The corresponding largest graph-piece sizes are $2,4,8$ in graphs of sizes $4,16,64$. Exact counting and the explicit partition give cover numbers $2,4,8$ in those cases. The script also examines all $2^{11}$ multilinear degree-at-most-two polynomials on four variables. Exactly eight vanish on (ra:1:cubic); their common zero set has nine points, including the spurious point $(1,1,1,0)$. These are finite exact checks of the local arguments, not experimental evidence for either answer to P versus NP.

Stress test and dependencies.

The lower bound counts representations of an entire relation, whereas the target permits an algorithm that only decides nonemptiness. The easy families above invalidate the inference from the former task to the latter. The isotropic-space maximum in Lemma 1.1 is existential; its proof is not a polynomial-time algorithm for finding that maximum. The quadratic-projection obstruction concerns a specified output language, not all data structures or Turing machines. These distinctions are instances of the compilation issues in [E7], and arise before applying the general barriers in [E2], [E3], [E4].

A stronger, still unproved route would have to give a syntax-sensitive elimination or decomposition algorithm whose total intermediate bit length and total arithmetic work are polynomial for every gate system (ra:1:gates). It would need to handle coupled nonlinear factors without flat affine expansion, without unbounded-degree expansion, and without hiding a satisfiability oracle inside a summary operation. The two simplest universal closure claims tested here are false; no substitute with these properties has been established.

Were that algorithm supplied, it would imply $\mathsf P=\mathsf{NP}$ and therefore $\mathsf{NP}=\mathsf{coNP}$ in Section 30006679. It would also rule out the one-way functions of Section 3403: for a given output $y$ and length $n$, the existence of a preimage extending any chosen prefix is an NP predicate; polynomially many prefix-extension decisions recover a preimage whenever one exists. This implication uses the exact length and any-preimage conventions of that entry. Conversely, failure of the two proposed representations establishes neither $\mathsf P\ne\mathsf{NP}$ nor existence of cryptographic hardness.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The obtained mathematics is the exact quadratic-graph affine-cover formula, a conditional-on-a-supplied-subspace solver, and two explicit obstructions to natural elimination schemes. These are proved within the restricted models stated above; their historical novelty has not been established. The attempt has not found either a general polynomial-time SAT algorithm or a superpolynomial lower bound for all such algorithms. Its useful negative conclusion is specific: small verifier syntax does not force small flat affine summaries, and conjunctions of visible quadratic equations are not closed under existential projection. A successful continuation must change the representation or the invariant, not merely sharpen constants in either failed claim.

Sources

• S1 Clay Mathematics Institute, The Millennium Prize Problems. https://www.claymath.org/library/monographs/MPPc.pdf. Catalogue formulation source.
• S2 P vs NP. https://www.claymath.org/millennium/p-vs-np/. Catalogue research/status reference; not a proof endorsement.
• S3 Constructive solvability and the P versus NP problem — Arne Hole. https://arxiv.org/abs/2406.16843. Catalogue research/status reference; not a proof endorsement.
• S4 PNP Labs — P versus NP formal reconstruction. https://pnplabs.com.au/. Catalogue research/status reference; not a proof endorsement.
• E1 Stephen Cook, The P versus NP Problem, Clay Mathematics Institute, Section 1 and Appendix. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf. Added primary source: Definitions and formulation. Consulted 24 September 2026.

• E2 Theodore Baker, John Gill and Robert Solovay, Relativizations of the $\mathcal P=?\mathcal{NP}$ Question, SIAM Journal on Computing 4$4$ $1975$, 431--442, oracle equality and separation results. https://doi.org/10.1137/0204037. Consulted 24 September 2026: publisher abstract; used only for the stated oracle obstruction, not a new proof audit.
• E3 Alexander A. Razborov and Steven Rudich, Natural Proofs, Journal of Computer and System Sciences 55$1$ $1997$, 24--35; author manuscript dated 30 November 1996, abstract and the natural-property/hardness framework. https://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf. Consulted 24 September 2026. The pseudorandomness assumption is retained; no unconditional barrier is asserted.
• E4 Scott Aaronson and Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory 1$1$ $2009$, Article 2; author manuscript, Sections 1--2 and 5, especially Theorems 5.1 and 5.3. https://www.scottaaronson.com/papers/alg.pdf. Consulted 24 September 2026: definitions and barrier statements.
• E5 Ryan Williams, Nonuniform ACC Circuit Lower Bounds, Journal of the ACM 61$1$ $2014$, Article 2, 32 pages; author manuscript, Theorem 1.1 and Section 1.1. https://people.csail.mit.edu/rrw/acc-lbs.pdf. https://doi.org/10.1145/2559903. Consulted 24 September 2026.
• E6 Lijie Chen, Avishay Tal and Yichuan Wang, Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits, ECCC TR26-039, 15 March 2026, abstract and reported $\mathsf E^{\mathsf{NP}}$ threshold-circuit bound. https://eccc.weizmann.ac.il/report/2026/039/. Consulted 24 September 2026: report page and abstract. A recent manuscript result, not an independent verification of its full proof.
• E7 Adnan Darwiche and Pierre Marquis, A Knowledge Compilation Map, Journal of Artificial Intelligence Research 17 $2002$, 229--264, Sections 1--2 and the separation of succinctness, queries and transformations. https://arxiv.org/abs/1106.1819. https://doi.org/10.1613/jair.989. Consulted 24 September 2026: article introduction and language definitions. Used as methodological context, not as the source of Lemma 1.1.