← P/NP Dual Rehearsal / Research Rounds / Round 20
Re-examining Ladner-style delayed diagonalization turns up an important correction: the controller's local computation cost can in fact be squeezed strictly into polynomial time; what genuinely can't be gotten for free is the global progress guarantee. The trick is to check only micro-inputs of length h(N)=O(log N) (both the number of candidates and brute-force SAT-solving cost only N^O(1)), paired with exponential throttling — delaying the full check on the i-th machine until the outer scale is large enough that h(N)^k_i≤N^c, since for any fixed k_i this condition will eventually hold. If candidate machine C_i really does equal SAT, then no counterexample ever exists, and the controller freezes there permanently — not a bug, but exactly the signal for P=NP. This gives rise to the Limit Separation Monitor (LSM): a computable stage function s(N) is constructed so that in a P≠NP world s(N)→∞, while in a P=NP world s(N) eventually stops at the first correct SAT machine. This rewrites the classical P/NP question precisely as the asymptotic observation problem of whether one fully computable trajectory “eventually stabilizes” or “advances without bound” — but no observation over any finite amount of time can decide limiting behavior; the monitor itself is not a decision procedure.
Relationship to other documents, stated as far as possible in the document's own words, not my interpretation.
“Finite witness search can be made very cheap through scale separation; but ‘a witness will never appear again’ or ‘a witness will eventually appear at every stage’ are limit semantics.” — from the “Verdict for This Round.” Provisional score P=NP: 19, P≠NP: 19 (“This score is probably also an eventual fixed point. (wry smile)”).
Loading…