← P/NP Dual Rehearsal / Research Rounds / Round 6
If, every time Team Not-Equal points out that some representation is large, Team Equal can simply reply “there's still some other, unknown representation,” then can every low-cost representation revolution be gathered together into one analyzable closure? This round builds a representation-transformation graph, only to immediately prove the Tractable-Reachability Equivalence lemma: L∈P if and only if there exists a uniform polynomial-time map sending L to a fixed tractable target — for SAT specifically, whether SAT can reach a tractable normal form is exactly synonymous with P=NP. This produces the round's central result, the “representation-closure paradox”: too wide a closure is merely a tautological restatement of the original problem, while too narrow a closure yields only restricted-model lower bounds. The research focus therefore shifts from “representation size” to “what is preserved under the transformation,” with Schaefer's dichotomy theorem and CSP polymorphism theory offered as success stories for the next step.
Relationship to other documents, stated as far as possible in the document's own words, not my interpretation.
“Too wide a closure ⇒ tautologically restates P/NP; too narrow a closure ⇒ yields only restricted-model lower bounds.” — from the “Closure Paradox” section of this paper. “‘Representation revolution’ cannot be sealed off once and for all by enumerating representations; but for the first time we can see clearly that a genuine candidate invariant should study ‘what the transformation preserves,’ not ‘what the representation looks like.’” — from the “Round Verdict” at the end of this paper. Score currently P=NP: 5, P≠NP: 5.
Loading…