# P/NP Debate Game Research Area | Round 6 ## Polynomial Representation-Transformation Closure and the Closure Dilemma: Can the Escape Hatch Be Formalized? **Round 06: Polynomial Representation-Transformation Closure and the Closure Dilemma** - **Lead Researcher:** Neo.K (Chuan-Wei Hsu) - **Collaborator/Editor:** Aletheia - **Institution:** EveMissLab (Yiyannuo Technology Co., Ltd.) - **Date:** August 1, 2026 - **Version:** v1.0 - **Research Status:** Round 6 Dual-Hypothesis Rehearsal - **Prerequisite Documents:** `00`–`05` - **Game Attitude:** Team Equality and Team Inequality continue to dismantle each other's models - **Document Standard:** Gamified narrative, formal mathematical boundaries --- ## Abstract Round 5 introduced the "Representation Escape Profile" (REP) and left a core question: If every time a lower bound appears for a certain representation, Team Equality can claim "there is another unknown representation," can Team Inequality incorporate all low-cost representation revolutions into an analyzable closure? This round attempts to establish a "Polynomial Representation-Transformation Closure." Let a representation system be a class of finite descriptions with equivalent semantics. If there exists a uniform, polynomial-time, polynomial-output-length transformation that preserves the problem's answer, a directed edge is drawn between the two representations. This yields a representation transformation graph or category. However, this round immediately uncovers a critical trap: **If arbitrary polynomial-time transformations are allowed, then "whether SAT can reach a tractable normal form" is completely equivalent to "whether SAT is in P."** If $P=NP$, the solver itself can directly compile any SAT instance into a constant TRUE or FALSE; conversely, as long as SAT can be compiled in polynomial time into a polynomially decidable target class, SAT is in P. This causes the "complete polynomial closure" to degenerate into a tautology of the original problem. Thus emerges the core "Closure Dilemma" of this round: $$ \boxed{ \text{Closure too broad}\Rightarrow\text{Tautology with }P/NP\text{;} \qquad \text{Closure too narrow}\Rightarrow\text{Only yields restricted model lower bounds.} } $$ Therefore, this round shifts the research direction from "blocking all representations" to "finding non-circular, independently definable transformation invariants that can preserve sufficiently many representation revolutions." In external theories, Schaefer-type Boolean CSP dichotomy theorems and the polymorphism approach of more general CSPs provide an important hint: sometimes what is truly stable is not the surface syntax, but the algebraic operations/relational closures preserved under certain classes of transformations. This provides an entry point for the next round: "The invariant is not size, but what algebraic structure is preserved." --- # 1. The Infinite Escape Hatch Left from the Previous Round After establishing the hardness matrix in Round 5, two simultaneous observations were obtained: 1. Strong lower bounds are usually tied to a specific model; 2. Elegant polynomial algorithms usually exploit some special representation or structure. Therefore, as long as Team Inequality says: $$ R_1\text{ is very large}, $$ Team Equality can reply: $$ R_1\rightarrow R_2\rightarrow R_3\rightarrow\cdots $$ Perhaps there exists an undiscovered $R_k$ that is very small. So this round first attempts to formalize the "representation revolution" itself. --- # 2. Representation Systems and Polynomial Transformations Let a representation system $$ \mathfrak R=(\mathrm{Rep},\llbracket\cdot\rrbracket,Q) $$ consist of: - $\mathrm{Rep}$: a set of finite descriptions; - $\llbracket r\rrbracket$: the semantics of representation $r$; - $Q$: the query of interest, such as SAT, model counting, equivalence, etc. An answer-preserving transformation between two representation systems $\mathfrak R_i, \mathfrak R_j$ is: $$ \tau_{ij}:\mathrm{Rep}_i\rightarrow\mathrm{Rep}_j, $$ satisfying: $$ Q(r)=Q(\tau_{ij}(r)). $$ If: $$ T_{\tau_{ij}}(|r|)\in\operatorname{poly}(|r|) $$ and: $$ |\tau_{ij}(r)|\in\operatorname{poly}(|r|), $$ then it is denoted as: $$ \mathfrak R_i\xrightarrow{\mathrm{poly}}\mathfrak R_j. $$ All such edges form a representation transformation graph: $$ \mathcal G_{\mathrm{rep}}=(\mathcal V,\mathcal E_{\mathrm{poly}}). $$ If $R'$ is reachable from an initial representation $R$ via a finite number of polynomial edges, it is denoted as: $$ R\leadsto_{\mathrm{poly}}R'. $$ Thus, the complete polynomial representation closure is defined as: $$ \operatorname{Cl}_{\mathrm{poly}}(R) = \{R'\mid R\leadsto_{\mathrm{poly}}R'\}. $$ --- # 3. Team Equality's First Move: Tractable Normal Forms Team Equality proposes: > $P=NP$ might be equivalent to the general representation of SAT being able to reach some tractable normal form within the polynomial representation closure. Let $\mathcal T$ be a tractable target representation family satisfying: $$ Q|_{\mathcal T}\in P. $$ For example, under certain fixed types: - 2-CNF; - Horn; - affine/XOR; - bounded-treewidth representations; - successfully compiled subfamilies of d-DNNF/OBDD. If there exists: $$ \tau:\mathrm{SAT}\rightarrow\mathcal T $$ such that $\tau$ is a uniform polynomial transformation and preserves satisfiability, then: $$ \mathrm{SAT}\in P. $$ So Team Equality writes its victory condition as: $$ \boxed{ \mathrm{SAT}\cap\operatorname{Reach}_{\mathrm{poly}}(\mathcal T)\neq\varnothing } $$ More colloquially: find a cheap "transformation route" to turn general SAT into a known easy world. --- # 4. Team Inequality's Counterattack: This Might Just Be Hiding the Answer in the Compiler Team Inequality immediately demands: > Can this transformation $\tau$ directly solve SAT during the conversion process? If there are no restrictions, assuming $P=NP$ and there is a decider $A$, one can define: $$ \tau_A(\varphi) = \begin{cases} \top,&A(\varphi)=1,\\ \bot,&A(\varphi)=0. \end{cases} $$ where $\top$ and $\bot$ are target representations of constant size with obvious answers. Since $A$ is polynomial time: $$ T_{\tau_A}\in P. $$ The output size is even: $$ O(1). $$ So if "arbitrary polynomial-time representation transformations" are allowed, then as long as $P=NP$, SAT can of course reach the simplest tractable normal form in one step. The reverse is also true: if there exists a polynomial-time transformation $$ \tau:\mathrm{SAT}\rightarrow\mathcal T $$ and the answer for $\mathcal T$ can be decided in polynomial time, then the composed algorithm: $$ \varphi \xrightarrow{\tau} \tau(\varphi) \xrightarrow{Q_{\mathcal T}} \{0,1\} $$ is a polynomial algorithm for SAT. Thus, we obtain the first formal lemma of this round. --- # 5. Complete Closure Trivialization Lemma ## Lemma 5.1 | Tractable-Reachability Equivalence Let $L$ be an arbitrary decision language, and $\mathcal T$ be a polynomially decidable language containing at least one fixed YES instance $t_1$ and one fixed NO instance $t_0$. The following two are equivalent: 1. $L\in P$; 2. There exists a uniform polynomial-time mapping $\tau$ such that: $$ x\in L \iff \tau(x)\in\mathcal T. $$ ### Proof If 2 holds, compute $\tau(x)$ first, then execute the P algorithm for $\mathcal T$, yielding $L\in P$. If 1 holds, let $A$ be the P decider for $L$, and define: $$ \tau(x) = \begin{cases} t_1,&A(x)=1,\\ t_0,&A(x)=0. \end{cases} $$ Then $\tau$ is polynomial time and preserves the answer. Q.E.D. --- ## Corollary If the "polynomial representation closure" allows all uniform P-time answer-preserving transformations, then: $$ L\text{ can reach a tractable normal form} \iff L\in P. $$ For SAT: $$ \boxed{ \mathrm{SAT}\leadsto_{\mathrm{poly}}\mathcal T \iff P=NP. } $$ So "whether it can escape to an easy representation" itself does not automatically provide new proof leverage. It merely rewrites the original problem as reachability on a graph. --- # 6. The Closure Dilemma This leads us to the truly important structure of this round: ## Too Broad If we allow: $$ \mathcal E=\text{all P-time answer-preserving transformations}, $$ then the closure problem is equivalent to the original $P/NP$ problem. No new information. ## Too Narrow If we only allow: - Local rewriting; - Fixed-size gadgets; - Specific algebraic operations; - Specific knowledge compilation languages; - Specific graph decompositions; - Specific proof systems; then even if we prove that SAT cannot reach a tractable normal form, we can only obtain: $$ \text{Unreachable within this transformation family}. $$ We still cannot deduce the general: $$ P\neq NP. $$ Therefore: $$ \boxed{ \text{The more complete the closure, the more circular; the more analyzable the closure, the more restricted.} } $$ This document refers to this as: $$ \boxed{ \text{Representation-Closure Dilemma} } $$ --- # 7. Team Equality Presses the Advantage: All "Transformations that Forbid Solving" Are Suspicious Team Inequality naturally wants to add a rule: > Fine, then we only allow structural transformations that "do not secretly solve SAT." Team Equality retorts: $$ \text{How do we formalize "not solving" without first knowing whether }P\stackrel{?}{=}NP\text{?} $$ For example, a global algebraic transformation might seem like mere rewriting, but it may have coincidentally completed the most critical reasoning. Conversely, a very local rewrite chain might also accumulate complete solving capabilities. So terms like "solution-oblivious," "not looking at the answer," or "just a representation transformation" easily become semantic slogans if they lack independent mathematical definitions. This shatters the second intuitive route: $$ \boxed{ \text{We cannot rely on natural language to distinguish between "truly solving" and "pure representation."} } $$ Computation itself is the transformation of states and representations. --- # 8. Team Inequality Changes the Question: Don't Block All Transformations, Find "Properties Preserved by a Class of Transformations" Since the complete closure is unanalyzable and restricted closures are not general enough, Team Inequality changes direction: > Instead of directly enumerating all possible representations, study which semantic/algebraic properties are preserved under a broad class of natural, independently definable transformations. That is, shifting from: $$ \text{Representation Size} $$ to: $$ \text{Transformation-Preserved Structure}. $$ This aligns with Round 5's idea: "Hardness might not be about size, but some structure that cannot be erased by representation revolutions." --- # 9. Hints from Schaefer's Dichotomy Theorem For a Boolean constraint language $\Gamma$, Schaefer-type results show that once the family of allowed relations is fixed, its SAT problem has a clear tractable/NP-complete boundary. Classic tractable cases include Horn, dual-Horn, bijunctive, affine, and constant-valid types; otherwise, it falls on the NP-complete side. This is extremely important because it shows: $$ \boxed{ \text{Certain hardness boundaries can indeed be determined by "what structure the allowed relations possess,"} } $$ rather than by the superficial length of the formula. More general finite-domain CSP dichotomy work further connects this boundary to polymorphism/algebraic operation structures. Therefore, we obtain a new hint that is very important for this series: > The cross-representation quantity truly worth looking for might not be "how many clauses there are," "how many states there are," or "how wide a certain graph is," but rather what operational structures that enable closure of reasoning are preserved/missing in the problem's semantics. --- # 10. Shifting from Representation Closure to Algebraic Closure Let $R\subseteq D^k$ be a relation. If an operation: $$ f:D^m\rightarrow D $$ acts coordinate-wise on any $m$ tuples in $R$ and still yields a tuple in $R$, then $f$ is said to preserve $R$. This type of preserving operation is the core of the polymorphism approach. For a constraint language $\Gamma$, one can examine: $$ \operatorname{Pol}(\Gamma). $$ The important point is: it is not the literal syntax of a certain CNF, but a description at the relational level of "which composition operations still maintain the feasible solution structure." This is extremely close to what we have been looking for in previous rounds: $$ \boxed{ \text{Structural properties that persist after changing representations.} } $$ But it must be emphasized: - The CSP dichotomy has resolved the classification of fixed constraint languages; - The relations allowed in general SAT are sufficient to express NP-complete structures; - Polymorphism theory itself does not directly prove $P\neq NP$. What it provides is a **demonstration of how to successfully establish a non-syntactic tractability invariant**. --- # 11. Team Equality's Counterattack: Schaefer Actually Supports Me Too Team Equality says: Schaefer doesn't just tell you "there are hard algebraic structures," it also tells you: $$ \text{Once a problem falls into certain special closures, the entire problem becomes P.} $$ This is exactly the spirit of the mathematical compressor that Team Equality has been searching for. For example, affine structures do not rely on checking all solutions, but rather switch to the linear algebra world: $$ Ax=b\pmod 2. $$ Horn structures also possess their own closure properties and efficient inference procedures. So Team Equality proposes: > Perhaps general SAT simply hasn't yet found a higher-order "hidden polymorphism / hidden normal structure." Team Inequality cannot use "it doesn't exist in currently known classifications" to prove non-existence. Therefore, the score remains tied. --- # 12. Knowledge Compilation Intervenes Again: Compilation Costs Cannot Be Invisible One of the core practices of Knowledge Compilation is to offline-transform the original representation into another target language, and then study: 1. Whether the target is succinct; 2. Which queries can be answered in polynomial time; 3. Which transformations can be completed in polynomial time. This is completely isomorphic to the representation graph of this round. But it simultaneously reminds us again: $$ T_{\mathrm{compile}} + L_{\mathrm{target}} + T_{\mathrm{query}} $$ must be measured together. If the query becomes linear time, but the target requires exponential size, a traditional $P=NP$ victory has not been achieved. If arbitrarily expensive offline preprocessing is allowed, it cannot be secretly excluded from uniform complexity. Therefore, this round retains the REP from Round 5 and adds a closure version of the cost: $$ \operatorname{PathCost} (R_0\rightarrow\cdots\rightarrow R_k) = \sum_{i=0}^{k-1} C(\tau_i) + L(R_k) + Q(R_k). $$ A truly effective escape path must be polynomial along the entire route. --- # 13. Establishing a "Representation Escape Hierarchy" Instead of a Single Closure To avoid the trivialization of the complete closure, this round first establishes a hierarchy for research purposes, without claiming it covers all algorithms: ## E0 | Surface Equivalence Rewriting - Clause reordering; - Boolean identities; - Constant propagation; - Obvious redundancy elimination. ## E1 | Local Gadgets and Definitional Extensions - Introducing a polynomial number of auxiliary variables; - Tseitin-style definitional encoding; - Bounded-local replacement. ## E2 | Structural Decomposition - Tree decomposition; - Backdoor decomposition; - Component decomposition. ## E3 | Algebraization / Geometrization - XOR linearization; - Polynomial encoding; - Polyhedral lifting; - Spectral/matrix representation. ## E4 | Knowledge Compilation - OBDD; - d-DNNF; - SDD and other target languages. ## E5 | Arbitrary Uniform P-time Answer-Preserving Transformations By E5: $$ \text{tractable reachability}\iff L\in P. $$ So E5 is no longer a proof tool, but the complete semantic boundary of the original problem. The value of this hierarchy lies not in claiming completeness, but in observing: $$ \text{At which layer is a candidate hard core actually penetrated?} $$ --- # 14. Erroneous Routes Eliminated in This Round The following statements must not be used directly as general $P\neq NP$ proofs: 1. SAT cannot be transformed into Horn by a known representation, therefore $P\neq NP$; 2. Putting all P-time transformations into the closure and proving that a tractable normal form is unreachable; 3. Defining "transformations that do not allow solving SAT" without independent formal conditions; 4. Directly defining the shortest path cost of the representation graph as the optimal algorithm time for SAT; 5. Using "unknown representations do not exist" as a premise; 6. Assuming all tractable normal forms must be of the existing Horn/2-SAT/affine types; 7. Directly extrapolating general $P\neq NP$ from fixed constraint-language dichotomies. --- # 15. True Achievements of This Round ## 15.1 Complete Closure Trivialization Obtained a clear equivalence: $$ \boxed{ L\in P \iff L\text{ can reach a fixed tractable target via arbitrary uniform P-time reduction.} } $$ Therefore, the "complete polynomial representation closure" cannot directly serve as a new proof breakthrough. ## 15.2 Discovery of the Closure Dilemma $$ \boxed{ \text{Too broad}=\text{Circular,} \qquad \text{Too narrow}=\text{Restricted.} } $$ This becomes a necessary filter for all subsequent "cross-representation blocking" schemes. ## 15.3 Shift in Research Focus No longer asking: $$ \text{Which of all representations is the smallest?} $$ But starting to ask: $$ \boxed{ \text{Which algebraic/semantic structures are still preserved under sufficiently broad and independently definable transformations?} } $$ ## 15.4 Schaefer/CSP Provides a Successful Paradigm CSP theory shows that tractability can indeed be linked to non-surface-syntactic closure/polymorphism properties. This is not the answer to $P/NP$, but it demonstrates what the invariants we seek should look like. --- # 16. Score Team Equality: - Proved that once the complete closure allows all P-time transformations, it can be directly compressed into a constant answer in a $P=NP$ world; - Shattered the idea that "representation reachability itself is a new proof tool." Team Inequality: - Found the circular trap of the complete closure; - Successfully shifted the research goal from representation size to transformation-preserved structures; - Found a direction with truly successful precedents from CSP/polymorphism. This round: $$ P=NP:5 \qquad P\neq NP:5. $$ Still a tie. --- # 17. Entry to Round 7 Next round's topic: ## The Battle for Algebraic Invariants: Is Tractability Always Accompanied by Some Preservable Operation? Core thought experiments: 1. Write the sources of "easiness" for Horn, 2-SAT, affine, and bounded-width CSPs as closures/polymorphisms; 2. Put the relation clone of general 3-SAT into the same perspective; 3. Let Team Inequality attempt to propose a generalized conjecture that "lack of sufficient polymorphism = uncompressibility"; 4. Let Team Equality point out that general algorithms can completely break away from fixed constraint-language representations, thus CSP invariants may not necessarily block P-time SAT solvers; 5. Search for whether there exist dynamic algebraic invariants that are higher-order than fixed polymorphisms and interact with computation trajectories / compilation closures. Tentative research formula: $$ \boxed{ \text{Tractability} \stackrel{?}{\Longleftrightarrow} \text{Existence of a family of operations that can be synthesized at low cost and preserve solution structures.} } $$ This is not a theorem; it is the debate topic for Round 7. --- # 18. External Theoretical References 1. A. Darwiche, P. Marquis, **A Knowledge Compilation Map**, JAIR 17 (2002), 229–264. 2. M. Cadoli, F. M. Donini, P. Liberatore, M. Schaerf, **Preprocessing of Intractable Problems**, Information and Computation 176(2), 2002. 3. T. J. Schaefer, **The Complexity of Satisfiability Problems**, STOC 1978. 4. A. Bulatov / D. Zhuk, series of works on finite-domain CSP dichotomy. 5. CSP algebraic approach: constraint languages, relational clones, polymorphisms, and tractability classification. --- ## Ruling for This Round $$ \boxed{ \text{The "representation revolution" cannot be sealed off once and for all by enumerating representations;} } $$ $$ \boxed{ \text{But for the first time we see clearly: true candidate invariants should study "what transformations preserve," not "what representations look like."} } $$ This pushes the research from a representation size game to a transformation-invariant structure game.