Current findings and proof limits

Why expanding an exhaustive search does not fix its size problem

A checked family of circuit examples shows a limit of expanding the existing exhaustive search. For these inputs, any accepted improvement needs a complete candidate list that eventually exceeds every polynomial bound in the encoded input length.

This rules out a polynomial-size guarantee for that fully materialized enumeration strategy, not every possible solver. It does not bound how many candidates a selective search must visit, rule out compressed or lazy methods, or claim that these examples arise from the SAT reduction. It does not settle P versus NP or earn additional proof-completion credit.

This correction adds no earned positive publication row or fixed checkpoint credit. Read the verified correction and its limits.

Why a complete local search can still miss a global improvement

The project has verified a limit of the implemented circuit search: no fixed cap on the number of gates checked together makes it a complete test for global minimality. For every such cap, a circuit can be made smaller even though the complete bounded search finds no accepted improvement. Every proper selected part, including disconnected selections, is already minimal when its boundary inputs are treated as independent.

The result rules out using this fixed-size local search alone to certify that an entire circuit is minimal. It does not settle P versus NP or rule out growing windows or transformations that use the surrounding circuit. A corrected route must still prove global coverage and polynomial runtime for the complete construction. This correction does not earn a positive milestone or increase the proof-completion estimate.

This correction adds no earned positive publication row or fixed checkpoint credit. Read the verified correction and its limits.

A verified limit on replacing parts of a circuit

The project has verified a counterexample to an unrestricted reading of the original report's replacement claim. The checked example has a smaller replacement for one part, but inserting it would create a circular dependency; the whole circuit was already minimal.

This does not invalidate the checked replacement results that enforce the necessary restrictions, and it does not settle P versus NP. It identifies a central obligation for the next research: derive the admissible replacements and show that the general method can use them without losing the required saving.

This correction adds no earned positive publication row or fixed checkpoint credit. Read the verified correction and its limits.

Latest earned milestone: M284.

Bounding the work needed to simplify an input

The project now proves a polynomial bound for the complete machine that reads an input and produces its reduced problem. It also proves that the machine for replaying the recorded simplifications can recover a valid original answer from a genuine solution of that reduced problem, within a polynomial bound.

This closes the running-time gap for these two defined phases, not for a complete solver. The remaining problem can still be unresolved, and this work does not find its solution. The replay bound starts with its encoded request; an additional machine to assemble that request is not claimed. The overall proof estimate is unchanged.

Risk-weighted proof completion estimate: 40%, with uncertainty 20% to 40%. Formal artefact coverage: 260 of 262 current scoped publication rows earned. Global gates closed: 0 of 5. Project-specific axioms remaining: 0. The eligible root theorem PNP.Main.p_eq_np remains absent and the publication gate is false.

P = NP is not established.

Read the source-bound milestone and limitations

Start here

P versus NP, this project, and what is actually proved.

Short answers come first. Technical terms appear only where they help, with links to the exact formal status for readers who want to audit the work.

Does this project prove that P equals NP?

No. The current result is that P = NP is not established. The repository records five formal blockers, no project-specific axioms, no eligible root theorem, and a closed publication gate.

What is P versus NP?

P contains problems that can be solved efficiently. NP contains problems whose proposed answers can be checked efficiently. The question asks whether every efficiently checkable problem can also be solved efficiently.

What does “machine-checked” mean?

The formal proof assistant Lean checks that each encoded proof step follows from its stated definitions, earlier theorems, and declared axioms. It does not make an unfinished argument complete, and it does not turn assumptions into proofs.

What did the latest milestone add?

The project now proves a polynomial bound for the complete machine that reads an input and produces its reduced problem. It also proves that the machine for replaying the recorded simplifications can recover a valid original answer from a genuine solution of that reduced problem, within a polynomial bound.

This closes the running-time gap for these two defined phases, not for a complete solver. The remaining problem can still be unresolved, and this work does not find its solution. The replay bound starts with its encoded request; an additional machine to assemble that request is not claimed. The overall proof estimate is unchanged.

Exact formal scope: For every raw input bitstring, the closed source-construction finite machine halts within its encoded-input polynomial bound and emits exactly the canonical source-derived contraction packet, with polynomial output size. On a decoded source system, the actual remaining core is satisfiable exactly when the original input is in CNFSAT. A separate closed finite-machine replay endpoint returns the exact canonical optional answer on every raw request. For the history generated from the actual source system, it lifts any genuine remaining-core model to a certificate accepted by the original source checker, with physical replay time bounded polynomially in the original input length. Projection and recovery preserve original models; source-generated history is not a caller-supplied correctness certificate.

Remaining boundary: A genuine model of the remaining core is still required for certificate recovery; this work does not find that model. A positive-dimensional stopped core remains unknown and may be satisfiable or unsatisfiable. The replay runtime bound starts from the canonical encoded request; a further finite-machine request assembler is not claimed. These are polynomial source-construction and witness-replay endpoints, not a complete residual decision procedure, manuscript residual-band minimizer, unconditional SaturatePositive, BCELReady or ZeroSlack, exact polynomial PCCMin, concrete CNFSAT membership in P, or eligible root theorem. P = NP is not proved.

Read the source-bound update.

Why did the progress figure change from 98% to about 40%?

The earlier 98% figure was a narrower scoped-row/editorial measure that readers could too easily interpret as proof completion. The current formal artefact coverage is 260 of 262 scoped publication rows earned, or 99.2% of the current evidence ledger. Evidence rows are not equal units of mathematical difficulty, and the denominator can grow when dependencies are discovered or split into smaller rows.

The two remaining global publication rows aggregate five large proof blockers. Adding completed local submilestones can therefore make the old ratio approach 100% while none of those load-bearing gates closes. Historical mentions of 98% are retained as superseded scoped-row/editorial estimates, not current proof-completion claims.

The replacement is a fixed 100-point, risk-weighted checkpoint model. It currently awards 40 points, so the risk-weighted proof completion estimate is 40%, with an uncertainty range of 20% to 40%. It can move down as well as up if assumptions, hidden complexity, invalidated dependencies, or new blockers are found.

Neither 40% nor 99.2% is confidence that P=NP is true, the probability that the proposed route is correct, or an estimate of time remaining. See the five tracks and global gates or inspect the canonical machine-readable tracker.

Why publish reports, coordinates, and hashes?

They let readers identify the exact source and files being discussed and detect drift. A matching hash proves file identity only; it does not prove the mathematics inside the file.

How can I follow new milestones?

Use the updates page or add the RSS/Atom feed to a feed reader. Each update has two plain-language paragraphs followed by a collapsed technical record.

Where should a technical reviewer begin?

Start at Technical review. It routes complexity theorists, Lean reviewers, and reproducibility reviewers to the report, formal status, architecture, source, and verification commands.

A precise one-sentence description.

“PNP Labs is formally reconstructing a proposed route to P = NP in Lean; the repository does not currently establish the theorem.”

Read formal status