← P/NP Dual Rehearsal / Research Rounds / Round 18
Follow the narrow path left by Round 17 all the way through: search for a fixed-degree short rejection certificate (UDRC) that works only for the i-th clocked machine and its designated diagonal input x_i. Actually pushing this path through reveals a new inverse-hardening phenomenon — if each machine is assigned only a small number of designed inputs, the diagonal language D becomes sparse by nature, and Hartmanis-Immerman-Sewelson proves that the existence of a sparse NP-P language is equivalent to a higher-order single-exponential deterministic/nondeterministic time separation. In other words, making the diagonal construction too thin doesn't lower the proof threshold — it may simultaneously upgrade it into a requirement to prove an even stronger separation. The other side of sparsification is Mahaney's theorem: the existence of a sparse NP-complete set would force P=NP, so a sparse diagonal set can't casually be allowed to double as NP-complete either. Switching to a dense route to dodge sparsity just turns the machine index and the clock exponent back into part of a unified input, reverting to the uniform-exponent barrier. Kleene-recursion-theorem-style self-reference can supply the addressing power to “point at yourself” — it doesn't automatically supply the compression power to “prove yourself” (the Self-Reference Compression Fallacy).
Relationship to other documents, stated as far as possible in the document's own words, not my interpretation.
“Making the diagonal slice too thin does not lower the proof threshold; it may raise it.” — from Section 5, “Sparsity Upward-Separation Trap.” “Self-reference can help us ‘point to ourselves,’ but cannot help us ‘prove ourselves’ for free.” — from the “Round Verdict” at the end of the document. Provisional score P=NP: 17, P≠NP: 17 (“It is now very hard to explain this as a ‘coincidence.’”).
Loading…