← P/NP Dual Rehearsal / Research Rounds / Round 4
Team Not-Equal deploys Tseitin graph parity constraints — for a connected graph, every vertex requires the parity sum of its incident edge variables to equal a specified charge; if the total charge is odd, the whole system is unsatisfiable, yet every proper subsystem is satisfiable, making it almost the ideal toy model of local–global divergence, and one that does carry exponential lower bounds in restricted proof systems such as resolution. Team Equal immediately counters: Tseitin constraints are essentially a linear system of equations over F₂ — summing all the vertex equations, each edge variable appears twice and cancels, and an odd total charge yields 0=1 directly — solvable in polynomial time by Gaussian elimination. Local–global divergence does not imply general computational hardness — the very same object can be compressed just by switching to a different algebraic coordinate system. Eliminates the overly strong thesis that “local hardness implies even greater global hardness,” and proposes a representation-escape tournament that can be expanded round by round, together with the representation-resistant coupling core (RRCC), as a long-term research goal — while explicitly warning that writing “hard under every representation” directly into the definition would just be smuggling P≠NP back into the name.
Relationship to other documents, stated as far as possible in the document's own words, not my interpretation.
“‘Local hardness, even greater global hardness’ is not the answer; the real question is whether the global structure can switch coordinate systems. To prove P≠NP, one must find a barrier that even a ‘representation revolution’ cannot escape.” — from the “Round Verdict” at the end of this paper. Score currently P=NP: 3, P≠NP: 3.
Loading…