# P/NP Debate Game Research Area | Round 5

## Representation Escape Tournament: Which Hardness is Pierced by Which Mathematical Weapon?

**Round 05: Representation Escape Tournament and Hardness Matrix**

- **Lead Researcher:** Neo.K (Chuan-Wei Hsu)
- **Collaborative Editor:** Aletheia
- **Institution:** EveMissLab (Eno Technology Co., Ltd.)
- **Date:** August 1, 2026
- **Version:** v1.0
- **Research Status:** Round 5 Dual-Hypothesis Rehearsal
- **Prerequisite Documents:** `00`–`04`
- **Game Attitude:** Let different mathematical representations brawl with each other; the document is still recorded according to formal research specifications.

---

## Abstract

The first four rounds gradually eliminated several overly simplified $P\neq NP$ routes: a large number of candidates does not mean item-by-item search is required; explosion under a fixed representation does not mean explosion across representations; local consistency with global contradiction might be directly compressed by a new mathematical coordinate system. The Tseitin parity case in Round 4 is particularly important: the same family of formulas can exhibit strong lower bounds in resolution-like proof systems, yet can be processed in polynomial time using Gaussian elimination in an $\mathbb F_2$ linear representation.

Therefore, Round 5 no longer guesses an "ultimate invariant" upfront, but adopts a representation escape tournament: selecting various classic hard families and feeding them into representation spaces such as logical proofs, algebraization, graph decomposition, knowledge compilation, monotone circuits, and linear extended formulations. We record where each family is compressed, where it still exhibits known lower bounds, and which conclusions cannot be extrapolated across models.

The most important observation of this round is: most known strong lower bounds are **representation-specific**, while known efficient escapes mostly rely on **identifiable structural conditions**. This shifts the research focus from "which problem is the hardest" to:

$$
\boxed{
\text{What structure determines whether a problem can find a low-cost representation escape?}
}
$$

We temporarily call this the **Representation Escape Profile (REP)**. It is not an invariant for proving $P\neq NP$, but a vectorized record of the compression/explosion patterns of a problem family under multiple representations. If, in the future, we can find an NP-complete problem family whose REP maintains a super-polynomial load across a sufficiently broad and provably complete family of representation transformations, only then might we truly approach the "representation-resistant coupling core."

---

# 1. Round 5 Game Rules

This round does not allow either team to declare victory based solely on a single representation.

For a problem family $\mathcal F$, we select several representation/calculus weapons:

$$
\mathfrak R
=
\{
R_{\mathrm{res}},
R_{\mathrm{alg}},
R_{\mathrm{mono}},
R_{\mathrm{decomp}},
R_{\mathrm{KC}},
R_{\mathrm{LP}}
\}.
$$

Respectively representing:

- resolution / proof systems;
- algebraic representations;
- monotone circuits;
- treewidth / separator / backdoor-type decompositions;
- knowledge compilation;
- LP extended formulations.

Only three types of rulings are allowed in each cell:

1. **Escape:** There are known efficient methods to compress the originally hard structure;
2. **Lower Bound:** There are known strong lower bounds in that restricted representation model;
3. **Unknown / Inextrapolable:** There are insufficient results, or the conclusions only restrict other models.

The most important rule is:

$$
\boxed{
\text{A "Lower Bound" in a cell }\neq\text{ General }P\neq NP
}
$$

And:

$$
\boxed{
\text{An "Escape" in a cell }\neq\text{ General }P=NP.
}
$$

---

# 2. Participating Problem Families

## 2.1 Tseitin / XOR-type Constraints

Its core is parity constraints on graphs. When encoded as CNF, it forms a classic hard family for resolution; but its semantic essence is $\mathbb F_2$ linear equations.

This family is the baseline contestant of Round 5 because it simultaneously demonstrates:

$$
\text{The same semantic problem}
\quad\text{can be hard in one representation and easy in another.}
$$

## 2.2 Pigeonhole Principle (PHP)

Pigeonhole principle formulas are a classic hard family in proof complexity. Haken-type results and subsequent works provide exponential size lower bounds for resolution, and strong lower bounds also exist for weak pigeonhole and sparse graph versions.

It is used to test:

$$
\text{Can combinatorial counting contradictions maintain hardness across representations?}
$$

## 2.3 Clique

Clique has classic super-polynomial/exponential lower bounds in monotone circuits; recent works continue to strengthen monotone lower bounds across different parameter ranges.

However, these results only restrict **monotone circuits**: general circuits can use negation, so they cannot be directly extrapolated to general circuit lower bounds.

## 2.4 General SAT and Structurally Restricted SAT

General SAT is the core $NP$-complete arena, but certain structural conditions can significantly reduce the difficulty. For example, bounded treewidth and small strong backdoors can bring SAT or #SAT into efficient or fixed-parameter tractable ranges.

This family is used to demonstrate:

$$
\text{The general class of NP-complete}
\neq
\text{Every structural subfamily is equally hard.}
$$

## 2.5 Polyhedral Representations of TSP / CUT / Stable Set

The natural polytopes of these combinatorial optimization problems have exponential extension complexity lower bounds in the LP extended formulation model: even if allowed to lift to higher dimensions and project back, there is no polynomial-size linear description of a certain type.

This is a very important case because it proves:

> "Adding auxiliary dimensions" cannot escape in all representation models.

However, this result still only rules out LP-type linear extended representations, not general algorithms.

---

# 3. Representation Escape Matrix

The "Lower Bound" in the table below refers to known restrictions in that model, not general computational lower bounds.

| Problem Family | Resolution / Proof | Algebraization | Monotone Circuit | Treewidth / Decomposition | Knowledge Compilation | LP Extended Formulation | General Algorithm Ruling |
|---|---|---|---|---|---|---|---|
| Tseitin / XOR | **Strong LB** (several resolution models) | **Escape**: $\mathbb F_2$ Gaussian elimination | Non-core result | Graph structure can affect solving | Some compilation languages may compress, depending on structure | Non-core model | **Linear semantics solvable in polynomial time** |
| Pigeonhole Principle | **Strong LB**: resolution exponential results | No general "one-hit pierce" conclusion | Non-core | Graph structure versions can change proof complexity | Varies by compilation language | Non-core | **Cannot infer general hardness from resolution LB** |
| Clique | Studiable in some proof systems | Non-linear general representation unsolved | **Strong LB**: monotone circuits | DP possible under specific graph width/parameters | Depends on representation language and parameters | Combinatorial optimization representation studies exist | **Monotone LB cannot extrapolate to general circuits** |
| SAT (General) | Various hard formula families have proof lower bounds | Some subclasses can be algebraized | Non-core | **Escape subfamilies**: bounded treewidth, small backdoor | **Clear tradeoff**: succinctness vs tractable queries | Not a primary general SAT model | **Core unknown** |
| TSP / CUT / Stable Set polytopes | Non-primary model | Other optimization representations may exist | Non-primary | Special graph classes can simplify | Non-core | **Strong LB**: no poly-size LP extension (for corresponding polytopes) | **LP LB cannot extrapolate to general algorithms** |

This matrix immediately demonstrates:

$$
\boxed{
\text{No single row can currently form a general lower bound across all columns simultaneously.}
}
$$

Nor can any single weapon form a universal escape across all rows.

---

# 4. Match 1: Tseitin Rematch — "Hardness" Might Just Be the Wrong Coordinates

## 4.1 Team Not-Equal Plays

In resolution, Tseitin formulas can form high proof width and long refutations. If we only look at CNF + resolution, this looks very much like a true global coupling barrier.

Team Not-Equal argues:

$$
\text{Local clause inference}
\rightarrow
\text{Requires large-scale global coordination}.
$$

## 4.2 Team Equal Counterattacks

Rewrite the parity constraints as:

$$
Ax=b\pmod 2.
$$

Gaussian elimination directly determines consistency in polynomial time.

Therefore, the high width of resolution is not a universal lower bound on the problem's semantics itself, but rather:

$$
\boxed{
\text{The representation mismatch cost of resolution for parity structures.}
}
$$

### Match Ruling

$$
\text{Team } P=NP \text{ wins a small round.}
$$

But we can only conclude:

> Certain seemingly globally hard CNF structures can be pierced by more suitable algebraic representations.

We cannot conclude general $P=NP$.

---

# 5. Match 2: Pigeonhole — Can Combinatorial Counting Contradictions Disappear by Changing Representations?

## 5.1 Team Not-Equal Plays

PHP is a classic source of resolution lower bounds. Existing results prove that generalized PHP and subsequent different versions require exponential-size resolution proofs, illustrating that some very simple combinatorial truths can be extremely expensive for specific proof systems.

This supports an important intuition:

$$
\text{Semantically "obvious"}
\not\Rightarrow
\text{Has a short proof in a certain formal system}.
$$

## 5.2 Team Equal Counterattacks

But what $P/NP$ asks is not:

$$
\text{Can resolution prove PHP shortly?}
$$

But whether all general polynomial algorithms are forced to pay a similar cost.

The combinatorial counting of PHP might be expressed much more shortly in stronger proof systems, arithmetic reasoning, or other representations.

Therefore:

$$
\boxed{
\text{proof-system hardness}
\neq
\text{general computational hardness}.
}
$$

### Match Ruling

Team Not-Equal obtains a **strong local weapon**, but fails to block all escape doors.

---

# 6. Match 3: Clique — The Monotone Circuit Big Bang

## 6.1 Team Not-Equal Plays

Clique is a classic battlefield for monotone circuit lower bounds. For certain parameter ranges, there are already super-polynomial or even strongly exponential monotone circuit lower bounds.

This looks very close to what we want:

$$
\text{The function itself is fixed, the circuit can be arbitrarily rearranged, yet it remains large.}
$$

## 6.2 Team Equal Counterattacks: You Banned Negation

Monotone circuits do not allow NOT gates. General circuits can use negation, possessing stronger representational power.

Therefore, the monotone lower bound proves:

$$
\operatorname{size}_{\mathrm{monotone}}(\mathrm{CLIQUE})
\text{ is large},
$$

Not:

$$
\operatorname{size}_{\mathrm{general}}(\mathrm{CLIQUE})
\text{ is large}.
$$

### Match Ruling

This round is extremely important for this project:

> "Cross-syntax" is not enough; true cross-representation must explicitly list the allowed computational primitives.

Once a new primitive is added, such as negation, XOR, extension variables, or oracle-like summaries, the original lower bounds might become invalid.

---

# 7. Match 4: SAT's Treewidth / Backdoor Escape

## 7.1 Team Equal Plays

General SAT is NP-complete, but if the constraint graph has bounded treewidth, or there exists a small strong backdoor such that assigning a few variables drops it into a tractable class, then decomposition can be used for efficient computation.

This illustrates:

$$
\boxed{
\text{Hardness is often concentrated in a small number of structures that "destroy decomposability".}
}
$$

If a small backdoor can be found, the originally large search space might rapidly collapse.

## 7.2 Team Not-Equal Counterattacks

This is not evidence for $P=NP$, because:

1. General SAT does not guarantee bounded treewidth;
2. The backdoor might be large;
3. Finding a small backdoor might itself be hard;
4. The exponential part of parameterized algorithms might be hidden in the treewidth or backdoor size.

The typical time can be written as:

$$
T(n,k)
=
\operatorname{poly}(n)\cdot f(k),
$$

If:

$$
k=\Theta(n),
$$

Then it could still be exponential time.

### Match Ruling

Team Equal successfully demonstrates that "structural conditions can collapse the NP-hard facade"; Team Not-Equal holds the "general worst-case" boundary.

---

# 8. Match 5: LP Extended Formulation — Lifting Dimensions is Not a Universal Escape Door

In Round 4, Team Equal frequently used a powerful counterattack:

> If the original space is hard to represent, introduce auxiliary variables, lift to a higher dimension, and project back.

Round 5 lets Team Not-Equal bring out extended formulation lower bounds.

For polytopes like the traveling salesman, cut, and stable set, results have proven that no polynomial-size linear extended formulation exists; even if higher-dimensional auxiliary spaces are allowed, exponential-size linear descriptions are still required.

Therefore:

$$
\boxed{
\text{Dimensional lifting can eliminate certain complexities, but it is not an infinite power in the world of linear representations.}
}
$$

## Team Equal Counterattacks

This still only restricts:

$$
\text{Linear inequalities + projection}
$$

this representation class.

General algorithms can be non-linear, discrete, recursive, dynamic, or completely bypass polyhedral descriptions.

### Match Ruling

Team Not-Equal secures an important principle:

> "Introducing new dimensions" itself cannot be treated as a perpetually valid representation escape axiom.

But it still does not block general computation.

---

# 9. Knowledge Compilation: A Shared Referee Stand for Both Teams

Knowledge compilation is particularly suitable for this project because it explicitly separates two things:

$$
\text{How succinct is the representation?}
$$

And:

$$
\text{Which queries/transformations can be completed in polynomial time?}
$$

A certain target language might be very succinct but not support certain tractable queries; another target language might support fast queries but require massive compilation results.

This perfectly aligns with our intermediate layer:

$$
\text{construct}
\rightarrow
\text{represent}
\rightarrow
\text{evaluate}.
$$

Thus, Round 5 yields a highly practical research discipline:

> Any proposal claiming "I turn an NP problem into an easily evaluable function" must simultaneously account for the generation cost and representation size of the function/structure.

Namely:

$$
T_{\mathrm{compile}}
+
L_{\mathrm{representation}}
+
T_{\mathrm{query}}.
$$

It cannot merely demonstrate:

$$
T_{\mathrm{query}}\in\operatorname{poly}(n).
$$

---

# 10. Representation Escape Profile (REP)

This round does not attempt to directly define an ultimate invariant, but first establishes descriptive tools.

For a problem family $\mathcal F$ and a representation family:

$$
\mathfrak R
=
\{R_1,\ldots,R_m\},
$$

Define its Representation Escape Profile:

$$
\operatorname{REP}(\mathcal F)
=
(E_1,E_2,\ldots,E_m),
$$

Where each $E_i$ records the following in representation $R_i$:

$$
E_i
=
(
C_{\mathrm{construct}},
L_{\mathrm{repr}},
T_{\mathrm{eval}},
M,
P_{\mathrm{precision}}
).
$$

The purpose of REP is not to say:

$$
\operatorname{REP}(\mathcal F)\text{ is large}
\Rightarrow
P\neq NP.
$$

It simply allows us to compare:

- Which problem families are hard in only one representation;
- Which problem families repeatedly explode across many representations;
- Which escapes rely on very specific algebraic structures;
- Which lower bounds are actually measuring the same deeper feature.

---

# 11. Common Patterns Emerging for the First Time in Round 5

Spanning the above cases, four recurring patterns can be observed.

## 11.1 Linearizable

If the global coupling of a problem can be transformed into:

$$
Ax=b
$$

or other algebraic systems with closed elimination rules, the massive combinatorial space might be directly folded.

Tseitin / XOR is the representative case.

## 11.2 Decomposable

If the constraint interaction graph can be cut by a small separator, bounded treewidth, or a small backdoor, the global problem can be synthesized from local tables.

Its basic form is:

$$
\text{global}
=
\operatorname{Combine}
(\text{small local summaries}).
$$

## 11.3 Compilable

If the problem can be translated into a target representation that makes subsequent queries easy, the search cost is shifted into compilation.

Whether this type of escape is truly polynomial depends on:

$$
L_{\mathrm{compiled}}
\quad\text{and}\quad
T_{\mathrm{compile}}.
$$

## 11.4 Primitive Upgrade

A model is hard, but adding new operational primitives might suddenly make it easy:

$$
\text{Resolution}+\mathrm{XOR}
$$

$$
\text{Monotone circuits}+\mathrm{NOT}
$$

$$
\text{Original space}+\text{extension variables}.
$$

Therefore, true lower bound research must answer:

> Why can't the "next primitive" save it either?

This question is closer to the core of $P\neq NP$ than proving hardness in a fixed model.

---

# 12. Team Not-Equal's New Strategy: Finding Families that are "Simultaneously Un-linearizable, Un-decomposable, Un-compilable, and Un-liftable"

Team Not-Equal no longer demands:

$$
\text{A certain representation size is large}.
$$

Instead, they propose a new thought experiment: finding an NP-complete family $\mathcal H_n$ that simultaneously resists several major escapes:

$$
\begin{aligned}
&\text{NoLowDimLinearize}(\mathcal H_n),\\
&\text{NoSmallSeparator}(\mathcal H_n),\\
&\text{NoSmallBackdoor}(\mathcal H_n),\\
&\text{NoSuccinctTractableCompilation}(\mathcal H_n),\\
&\text{NoSmallExtension}(\mathcal H_n).
\end{aligned}
$$

These are currently just research conditions, not properties proven to co-exist.

Team Not-Equal's long-term goal is to establish some kind of:

$$
\boxed{
\text{Escape Coverage Incompleteness Theorem}
}
$$

That is, proving that a sufficiently large family of polynomial algorithms must fall into some analyzable structural escape pattern; and then providing corresponding lower bounds for each pattern.

But this step is extremely difficult, because if we could truly establish a finite complete classification for "all polynomial algorithms," we would already be close to solving the original problem.

---

# 13. Team Equal's New Strategy: The Representation Revolution Hypothesis

Team Equal pushes the inspiration from the video to its maximum:

> Historically, many problems that "seemed to require massive branching" were ultimately solved not by faster enumeration, but by finding new mathematical representations.

Thus, they propose:

$$
\boxed{
\text{Representation Revolution Hypothesis}
}
$$

Namely, for the existential quantifier of SAT, there might exist a new representation primitive $R_*$, not yet included in the above matrix, such that:

$$
C_{\mathrm{construct}}(R_*)
+
L(R_*)
+
T_{\mathrm{eval}}(R_*)
\in
\operatorname{poly}(n).
$$

Team Equal does not need to know what $R_*$ is right now; but if Team Not-Equal wants to prove $P\neq NP$, they must rule out all possible $R_*$, rather than just ruling out known representation languages.

This is the most troublesome ultimate escape hatch for the $P\neq NP$ side.

---

# 14. Erroneous Routes Eliminated in This Round

The following arguments are officially blacklisted:

1. Resolution exponential lower bound $\Rightarrow P\neq NP$;
2. Monotone circuit exponential lower bound $\Rightarrow$ General circuit exponential lower bound;
3. LP extension complexity exponential lower bound $\Rightarrow$ No general polynomial algorithm exists;
4. Bounded treewidth SAT is easy $\Rightarrow$ General SAT is also easy;
5. A representation can be queried efficiently $\Rightarrow$ The compilation itself is also efficient;
6. Introducing auxiliary dimensions can always compress hardness;
7. All currently known representations fail $\Rightarrow$ No unknown representation revolution exists.

---

# 15. Tentative Results of This Round

## 15.1 Result 1: Establishing the "Representation Escape Matrix"

The research begins to shift from a single route to cross-model comparisons, rather than letting each lower bound claim self-victory within its own model.

## 15.2 Result 2: Hardness and Representation Form a Binary Relation

The more accurate object of study is not:

$$
\operatorname{Hardness}(F),
$$

But:

$$
\operatorname{Hardness}(F\mid R).
$$

Only when we can control the family of representation transformations are we qualified to discuss cross-representation hardness.

## 15.3 Result 3: Representation Revolution is Team Equal's Strongest Escape Hatch

As long as some unknown $R_*$ exists, all current local lower bounds might still be bypassed.

## 15.4 Result 4: Team Not-Equal's Goal Shifts from "Finding a Lower Bound" to "Restricting the Space of Representation Revolutions"

The next step is to ask not just:

$$
\text{Which representation is hard?}
$$

But:

$$
\boxed{
\text{Do all representation revolutions realizable in polynomial time share certain finitely classifiable structures?}
}
$$

---

# 16. Round Score

In Round 5:

- Team Equal uses Tseitin linearization and SAT treewidth/backdoor to prove once again that representation revolutions can indeed occur;
- Team Not-Equal uses resolution, monotone circuits, and LP extension complexity to prove that certain representation escape doors can indeed be strictly sealed.

Therefore, each team scores one point this round:

$$
P=NP:4
\qquad
P\neq NP:4.
$$

The score is just a game interface, not mathematical evidence.

---

# 17. Gateway to Round 6: Can Representation Transformations Themselves Be Classified?

The real new question left by Round 5 is:

$$
\boxed{
\text{If any unknown representation can be used to escape, how can we possibly prove cross-representation lower bounds?}
}
$$

So Round 6 will study:

## **Polynomial Representation Transformation Closure**

Suppose there exists a polynomial-time compilation between two representations $R_i, R_j$:

$$
R_i\xrightarrow{\operatorname{poly}}R_j.
$$

Can we form a transformation graph/category out of all representation transformations that "do not add super-polynomial resources":

$$
\mathfrak C_{\mathrm{poly}}?
$$

And then ask:

1. Which lower bounds are preserved under this closure?
2. Which hardness is merely a representation artifact?
3. Is it possible for a canonical / minimal representation class to exist?
4. If $P=NP$, does it mean SAT has a tractable normal form in this closure?
5. If $P\neq NP$, can it be formulated as SAT being unable to reach any tractable normal form within this closure?

This will, for the first time, turn "representation revolution" into a studiable mathematical object, rather than an infinite unknown escape door.

---

# 18. External Theoretical References

1. Darwiche, A.; Marquis, P. **A Knowledge Compilation Map.** *Journal of Artificial Intelligence Research* 17 (2002), 229–264. Its core framework compares the succinctness of representation languages and the queries/transformations they can support in polynomial time.
2. Ben-Sasson, E.; Wigderson, A. **Short Proofs Are Narrow—Resolution Made Simple.** *Journal of the ACM* 48(2), 2001. Links resolution proof width with proof length, unifying various classic exponential lower bounds.
3. de Rezende, S. F.; Nordström, J.; Risse, K.; Sokolov, D. **Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.** CCC 2020.
4. Razborov / Alon–Boppana series and subsequent monotone circuit works: Clique has strong lower bounds in the monotone circuit model; but this restriction cannot be directly extrapolated to general circuits.
5. Fiorini, S.; Massar, S.; Pokutta, S.; Tiwary, H. R.; de Wolf, R. **Exponential Lower Bounds for Polytopes in Combinatorial Optimization.** *Journal of the ACM* 62(2), 2015. Provides exponential LP extension complexity lower bounds for polytopes such as TSP, cut, and stable set.
6. Gaspers, S.; Szeider, S. **Strong Backdoors to Bounded Treewidth SAT.** Studies how small backdoors and bounded treewidth form tractable structural gateways for SAT / #SAT.

---

## Round Ruling

$$
\boxed{
\text{Round 5 did not find a cross-representation invariant, but for the first time, it mapped out "where hardness lies, and where it escapes."}
}
$$

$$
\boxed{
\text{The next step is no longer to chase after every representation, but to study "polynomial representation transformations" themselves.}
}
$$