← P/NP Dual Rehearsal / Research Rounds / Round 21
Places Round 20's Limit Separation Monitor inside the arithmetical hierarchy: P=NP is equivalent to ∃i∀x R(i,x), a Σ₂⁰-type statement; P≠NP is equivalent to ∀i∃x¬R(i,x), a Π₂⁰-type statement, and the monitor's eventual-stabilization/unbounded-advance dichotomy corresponds exactly to this quantifier swap. Further, by embedding the standard c.e. sets FIN (finite) and INF (infinite), it's proved that for a general monotone computable monitor, the stabilization problem can reach Σ₂⁰-completeness and the unboundedness problem can reach Π₂⁰-completeness — so there is no certificate system, universal across all monitors, of the form “guess a finite witness, verify it with a computable verifier.” But the most important safeguard against misreading this round is: this must never be swapped in for “P/NP has no finite mathematical proof.” P/NP is a fixed proposition, not an index problem of the form “feed in an arbitrary monitor and ask yes/no”; an inductive proof can already cover ∀n in finitely many steps by its very nature. So this round splits finite certificates into three tiers — Prefix Witness, Uniform Mechanical Certificate, and Structural Mathematical Proof — and only the third tier is the genuine opening where P/NP remains open; any argument that claims to cover an infinite obligation with a finite proof owes a Quantifier Compression Debt (QCD), and must account for its generalization mechanism.
Relationship to other documents, stated as far as possible in the document's own words, not my interpretation.
“The monitor can reveal the quantifier structure of P/NP, but cannot eliminate those quantifiers relying on finite observation.” — from the “Ruling for This Round.” Provisional score P=NP: 20, P≠NP: 20 (“This is no longer score control. Now it's more like: every time we find a loophole, the other team simultaneously obtains its dual version — some kind of ‘conservation of dual proof obligations.’”).
Loading…