# P/NP Debate Game Research Area | Round 14

## Complexity Potential Game: Amortized Tractability Certificates, Potential Escape, and the Certificate-Completeness Trap

- **Lead Researcher:** Neo.K (Chuan-Wei Hsu)
- **Collaborative Organization:** Aletheia
- **Institution:** EveMissLab (Eno Technology Co., Ltd.)
- **Date:** August 1, 2026
- **Version:** v1.0
- **Research Status:** Round 14 Dual-Hypothesis Rehearsal
- **Prerequisite Document(s):** `13_Round_13_Tractable_Closure_Stability_and_Polynomial_Chain_Explosion.md`
- **Game Stance:** Team Equality and Team Inequality continue to undermine each other
- **Document Standard:** Formal propositions, candidate conjectures, thought experiments, external references, and game scores are recorded separately

---

## Abstract

Round 13 proved: Even if each step of dynamic representation conversion takes polynomial time relative to the current representation size, if the conversion depth grows with the input, or the intermediate representations continuously inflate, the entire trajectory may still exceed any fixed polynomial bound. Therefore, Team Equality proposed the **Amortized Tractability Certificate (ATC)**: Instead of claiming step-by-step that "this step is easy," it seeks a global potential function to control the total cost of the entire representation/bridge/quotient path in an amortized manner.

This round first connects this idea to standard amortized analysis. If the actual cost at step $t$ is $c_t$, and the state potential is $\Phi_t\ge 0$, we define the amortized cost:

$$
\widehat c_t
=
c_t+\Phi_{t+1}-\Phi_t.
$$

Then by telescoping sum:

$$
\sum_{t=0}^{m-1}c_t
=
\sum_{t=0}^{m-1}\widehat c_t
+
\Phi_0-\Phi_m.
$$

Thus, as long as the initial potential and the total amortized cost are both bounded by a fixed polynomial of the original input size, and $\Phi_m\ge0$, the total actual computational cost is polynomial. This provides a truly rigorous template for a "dynamic switching full-path cost certificate."

However, this round immediately discovered a crucial asymmetry. For the $P=NP$ side, there only needs to exist **one** polynomial-time SAT algorithm and its algorithm-specific potential function; thus, the previous requirement that the potential must be solver-independent was too strong for Team Equality. Conversely, if the $P\neq NP$ side wants to use "the inability to find a certain potential function" as a lower bound, they must first prove that the potential function language is complete for all polynomial-time algorithms. Otherwise, the absence of a certificate merely means the certificate system is too weak, not that the algorithm does not exist.

This forms the core of this round: the **Potential Certificate Completeness Trap**:

$$
\text{Certificate system too weak}
\Rightarrow
\text{Misses true }P\text{ algorithms},
$$

$$
\text{Certificate system too strong}
\Rightarrow
\text{Easily smuggles the original problem itself, such as "optimal remaining solving time," into the potential}.
$$

External program analysis research provides a good reference: potential-based automatic amortized resource analysis can indeed derive polynomial runtime bounds in restricted programming languages, and certain restricted typability results even correspond to PTIME. However, for general Turing machines, "whether it runs in polynomial time" cannot be universally decided by a single algorithm. Therefore, potential functions are highly suitable as **constructive upper-bound certificates**, but they cannot be directly inverted into general lower bounds before establishing the completeness of the certificate system.

Finally, this round upgrades the ATC into a two-layer certificate:

1. **Progress / Ranking Layer**: Controls trajectory depth and termination;
2. **Amortized Potential Layer**: Controls total resource expenditure.

It also advances Round 15 to the "Tractability Proof System": Can we establish a non-circular, verifiable polynomial tractability proof language that is complete for a sufficiently broad class of algorithms?

---

# 1. Questions Left from the Previous Round

Round 13 yielded:

$$
\boxed{
\text{Stepwise Polynomiality}
\not\Rightarrow
\text{Pathwise Polynomiality}
}
$$

For example:

$$
s_{t+1}=s_t^2
$$

Each step is a polynomial transformation, but after $m$ steps:

$$
s_m=n^{2^m}.
$$

Therefore, the Dynamic Tractable Closure Scheme cannot merely prove that each:

$$
R_t\rightarrow R_{t+1}
$$

is easy, but must control the peak size, cumulative cost, and depth of the entire:

$$
R_0\rightarrow R_1\rightarrow\cdots\rightarrow R_m
$$

Team Equality thus proposed:

$$
\boxed{\mathrm{ATC}
=
\text{Amortized Tractability Certificate}}
$$

This round asks:

> Can we, like amortized data structures, use a global potential ledger to prove that although some steps of SAT's dynamic quotient/bridge portfolio are expensive, the total cost remains polynomial?

---

# 2. Standard Potential Method: A Truly Usable Mathematical Template

Let the algorithm state at step $t$ be:

$$
Z_t,
$$

which can simultaneously include:

$$
Z_t
=
(R_t,\mathcal B_t,\mathcal M_t,\mathcal D_t,\ldots),
$$

For example:

- Current representation $R_t$;
- Current bridge language $\mathcal B_t$;
- Memory/learned information $\mathcal M_t$;
- Unsettled quotient/bridge debt $\mathcal D_t$.

Let the actual cost at step $t$ be:

$$
c_t\ge0.
$$

Choose a non-negative potential function:

$$
\Phi:Z\rightarrow\mathbb R_{\ge0}.
$$

Denote:

$$
\Phi_t=\Phi(Z_t).
$$

Define the amortized cost:

$$
\boxed{
\widehat c_t
=
c_t+\Phi_{t+1}-\Phi_t
}
$$

Then:

$$
c_t
=
\widehat c_t+\Phi_t-\Phi_{t+1}.
$$

Summing over all steps:

$$
\boxed{
\sum_{t=0}^{m-1}c_t
=
\sum_{t=0}^{m-1}\widehat c_t
+
\Phi_0-\Phi_m
}.
$$

This is the telescoping structure of the standard potential method.

---

# 3. ATC Upper Bound Proposition

## Proposition 3.1: Polynomial Amortized Certificate

Assume that for an input of length $n$, the computation trajectory of a candidate algorithm $A$:

$$
Z_0,Z_1,\ldots,Z_m
$$

satisfies:

$$
m\le q(n),
$$

where $q$ is a fixed polynomial;

and there exists a non-negative potential function $\Phi_A$ such that:

$$
\Phi_A(Z_0)\le r(n),
$$

where $r$ is a fixed polynomial;

and the amortized cost of each step satisfies:

$$
\widehat c_t
=
c_t+\Phi_A(Z_{t+1})-\Phi_A(Z_t)
\le p(n),
$$

where $p$ is a fixed polynomial.

Then:

$$
\sum_{t=0}^{m-1}c_t
\le
q(n)p(n)+r(n),
$$

Thus, the total runtime cost is polynomial.

### Proof

By the telescoping formula and $\Phi_m\ge0$:

$$
\sum c_t
=
\sum\widehat c_t+\Phi_0-\Phi_m
\le
\sum\widehat c_t+\Phi_0.
$$

Also, since:

$$
m\le q(n),
\qquad
\widehat c_t\le p(n),
$$

Therefore:

$$
\sum\widehat c_t
\le
q(n)p(n).
$$

Thus:

$$
\sum c_t
\le
q(n)p(n)+r(n),
$$

which is a fixed polynomial. □

---

# 4. First Important Correction: The Potential Function is Not an Algorithm

If a SAT solver fundamentally lacks a polynomial-time actual computation trace, writing an arbitrarily beautiful potential cannot suddenly make it polynomial.

What the potential function does is:

$$
\boxed{
\text{Prove/analyze the total cost of an existing computation}
}
$$

Rather than:

$$
\boxed{
\text{Perform unfinished work on behalf of the computation}
}
$$

Therefore:

$$
\text{Potential Method}
\neq
\text{New computational model}.
$$

It is a meta-level cost certificate.

This differs from the initial video's "mathematical constructs can become algorithms":

- The functions in the video enter the state transition themselves, belonging to object-level computation;
- If the potential in this round is only used to analyze the total cost, it belongs to meta-level proof.

If $\Phi$ is to truly become part of the algorithm, it must be efficiently computable and participate in decision-making, in which case its computational cost must also be re-accounted into:

$$
T_{\mathrm{total}}.
$$

---

# 5. Second Important Correction: Solver-Independent is Too Strong for Team Equality

Round 13 described the ideal potential as solver-independent, answer-blind, cross-representation, and non-circular.

This round discovers that the first item needs to be split into two use cases.

## 5.1 For the $P=NP$ Side

To prove:

$$
P=NP,
$$

there only needs to exist **one** deterministic polynomial-time SAT algorithm:

$$
A^\star.
$$

Therefore, it is completely permissible to use:

$$
\Phi_{A^\star}.
$$

That is, an algorithm-specific potential.

This is entirely consistent with general amortized analysis: the potential function of one data structure does not need to simultaneously analyze all data structures.

So:

$$
\boxed{
\text{The }P=NP\text{ side does not need a universal potential.}
}
$$

## 5.2 For the $P\neq NP$ Side

If one wants to prove:

$$
P\neq NP,
$$

one must rule out all candidate algorithms.

If Team Inequality wants to say:

> "I proved that SAT does not have this kind of potential, so it is not in P."

They must first establish:

$$
A\in P
\Longrightarrow
A\text{ necessarily possesses this type of potential certificate}.
$$

That is, the **completeness** of the certificate system.

Otherwise, a polynomial algorithm might simply not fall into this proof template.

Therefore:

$$
\boxed{
\text{Potential is highly suitable for proving upper bounds,}
}
$$

$$
\boxed{
\text{but "no potential" usually cannot directly prove lower bounds.}
}
$$

---

# 6. Potential Certificate Completeness Trap

Let:

$$
\mathfrak P
$$

be a potential function certificate language, such as:

- Linear potential;
- Polynomial potential;
- Fixed-dimension feature potential;
- Lexicographic ranking;
- Weighted combination of treewidth/backdoor/width;
- Automatic amortized resource analysis type.

If:

$$
A\text{ has no }\mathfrak P\text{-certificate},
$$

it can only imply:

$$
A\notin\operatorname{Cert}(\mathfrak P).
$$

Unless it is additionally proven that:

$$
P
\subseteq
\operatorname{Cert}(\mathfrak P).
$$

This is the:

$$
\boxed{
\text{Potential Certificate Completeness Trap}
}
$$

### Weak Certificate System

If:

$$
\operatorname{Cert}(\mathfrak P)
\subsetneq P,
$$

then the absence of a certificate cannot serve as a $P$ lower bound.

### Overly Strong Certificate System

If we allow:

$$
\Phi_A(Z)
=
\text{the optimal remaining runtime starting from }Z,
$$

it certainly describes the cost precisely, but "characterizing $\Phi_A$" has already stuffed the entire original problem back into the potential.

Or defining:

$$
\Phi(F)
=
\min_A T_A(F),
$$

then "whether $\Phi$ is polynomial" is almost the original problem itself.

Therefore:

$$
\boxed{
\text{Overly strong potential}
\Rightarrow
\text{Circular / Tautological}.
}
$$

---

# 7. External References: AARA, Ranking Functions, and General Runtime Verification

Potential-based resource analysis already has mature forms in program analysis. Automatic Amortized Resource Analysis (AARA) uses type systems/potential annotations to derive resource bounds; existing work has established polynomial potential type systems and studied the relationship between typability and PTIME in restricted fragments.

This provides two contrasting insights for this round:

1. A sufficiently good potential proof language can indeed cover a very large polynomial-time program family;
2. This completeness must be rigorously proven under explicit restrictions and cannot simply jump out from "potential is very natural."

On the other hand, for general Turing machines, existing results prove: there is no algorithm that can universally decide for all machines "whether it runs within a certain polynomial time bound." Therefore, one cannot expect a universal, fully automatic, sound+complete polynomial-runtime analyzer.

Ranking functions are primarily used to prove termination. Existing research also shows that while some terminating systems have ranking functions, the ranking expression itself may require a very large representation. Therefore:

$$
\text{Existence of a certificate}
\neq
\text{Existence of a small certificate}.
$$

However, a large certificate still does not automatically change the complexity class of the analyzed algorithm itself.

---

# 8. ATC Upgrade: Two-Layer Certificate

A single $\Phi$ simultaneously controlling trajectory termination, bridge depth, representation size, and runtime is prone to confusion.

This round therefore upgrades the ATC into two layers.

## 8.1 Progress / Ranking Layer

Define:

$$
\rho(Z_t)
$$

taking values in a well-founded ordered set, requiring:

$$
\rho(Z_{t+1})<\rho(Z_t)
$$

to hold for true high-level transitions.

If:

$$
\rho(Z_0)\le q(n)
$$

and each step decreases by at least one discrete unit, then:

$$
m\le q(n).
$$

It controls:

$$
\boxed{\text{Bridge Depth / Termination}}
$$

## 8.2 Amortized Potential Layer

Use:

$$
\Phi(Z_t)\ge0
$$

to control total resources:

$$
\widehat c_t
=
c_t+\Phi(Z_{t+1})-\Phi(Z_t).
$$

If:

$$
\widehat c_t\le p(n),
\qquad
\Phi(Z_0)\le r(n),
$$

Then:

$$
T_{\mathrm{total}}
\le
q(n)p(n)+r(n).
$$

The complete certificate is written as:

$$
\boxed{
\mathrm{ATC}(A)
=
(\rho_A,\Phi_A,p,q,r)
}
$$

---

# 9. Team Equality Plays a Card: Adaptive Potential Portfolio

Team Equality proposes:

> Since the representation is constantly changing, why must I use a fixed structural potential?

They propose piecewise potential functions:

$$
\Phi^{(1)},
\Phi^{(2)},
\ldots,
\Phi^{(k)}
$$

corresponding respectively to:

- CNF elimination;
- XOR subsystem;
- compiled component;
- bridge coordination;
- learned-clause phase.

As long as during a phase switch there exists:

$$
\Phi^{(j+1)}(Z)
\le
a\Phi^{(j)}(Z)+b(n),
$$

and all switching accumulations still have a global polynomial budget, a piecewise ATC can be established.

Team Equality's new slogan:

$$
\boxed{
\text{I don't need the same global ruler,}
}
$$

$$
\boxed{
\text{I just need to prove that changing rulers is itself affordable.}
}
$$

---

# 10. Team Inequality Counterattacks: Four Types of Potential Escape

## 10.1 Plateau

A long trajectory exists, but:

$$
\Phi(Z_{t+1})\approx\Phi(Z_t),
$$

there is not enough potential drop to pay for the actual cost.

## 10.2 Cycle

Representations cycle among:

$$
R^{(A)}
\rightarrow
R^{(B)}
\rightarrow
R^{(C)}
\rightarrow
R^{(A)}
$$

If each set of local potentials decreases in its own coordinates, but becomes "fully recharged" again after switching, double-counting may occur.

## 10.3 Hidden Debt

A certain potential decreases, but:

$$
\text{precision},
\text{representation size},
\text{witness lift},
\text{bridge arrangement}
$$

other costs among them surge.

## 10.4 Coordinate Escape

The potential in one representation is very large, and suddenly becomes small after converting to another representation, but the actual semantic work has not been completed.

So every coordinate change must have:

$$
D_{\mathrm{switch}}
$$

and a provable bridge inequality.

---

# 11. Finite Structural Feature Potentials are Not Automatically Complete

Assume:

$$
\Phi(F)
=
a_1\operatorname{tw}(F)
+
a_2\operatorname{bd}(F)
+
a_3\operatorname{width}(F)
+
a_4\operatorname{sym}(F)
+\cdots
$$

This can be a very good empirical/heuristic potential, but it cannot automatically become a P/NP proof tool.

Reasons include:

1. Some P problems may also be very large on some of these metrics;
2. Unknown algorithms might utilize new structures not listed;
3. Different representations can change the parameters;
4. The completeness of a fixed finite feature vector is unproven.

Existing empirical studies on SAT solvers also show that single metrics like treewidth, backdoor, backbone, and community structure have limited explanatory power for CDCL runtime, and multi-parameter combinations are often better.

This supports:

$$
\text{A single structural parameter is often insufficient}
$$

but does not support:

$$
\text{A finite parameter vector is sufficient to prove general SAT lower bounds}.
$$

---

# 12. The Most Important Asymmetry of This Round

## The $P=NP$ Side

Only needs:

$$
\boxed{
\exists A\;
\exists \mathrm{ATC}_A
}
$$

such that $A$ precisely decides SAT, and the ATC proves:

$$
T_A(n)\in\operatorname{poly}(n).
$$

## The $P\neq NP$ Side

If one wants to use "ATC does not exist" to prove separation, one must first establish:

$$
\boxed{
\forall A\;
[
A\in P
\Rightarrow
\exists \mathrm{ATC}_A
]
}
$$

plus:

$$
\forall A\text{ solving SAT},
\quad
\neg\exists\mathrm{ATC}_A.
$$

The first condition itself is:

$$
\boxed{
\text{Certificate system completeness}
}
$$

Therefore:

$$
\boxed{
\text{The potential function method is not a symmetric weapon for }P=NP\text{ and }P\neq NP\text{.}
}
$$

It naturally leans toward the upper-bound / constructive side.

---

# 13. Meta-Level Cost and Object-Level Cost Separated Again

This round establishes three levels:

### Level 1: Object Runtime

$$
T_A(n).
$$

This is the true object of classification in traditional $P/NP$.

### Level 2: Runtime Certificate Complexity

$$
C_{\mathrm{cert}}(A).
$$

How complex it is to prove the runtime bound of $A$.

### Level 3: Discovery Complexity

$$
C_{\mathrm{discover}}(A,\mathrm{ATC}).
$$

The cognitive cost an agent must pay to find the algorithm and proof.

The three can be coupled, but cannot be conflated:

$$
C_{\mathrm{cert}}\text{ is large}
\not\Rightarrow
T_A(n)\text{ is large}.
$$

---

# 14. Erroneous Routes Eliminated in This Round

The following arguments may no longer be used alone for traditional $P\neq NP$:

1. "I can't find a beautiful potential function, so SAT is not in P."
2. "A certain structural potential cannot decrease, so any algorithm is slow."
3. "A certain automatic resource analyzer fails to analyze, so the program is not polynomial."
4. "The runtime certificate is large, so the algorithm itself is slow."
5. "The potential function value decreases, so the actual computation must be making progress." — Unless there is a transition inequality.
6. "Different phases each have their local potential, so it is globally automatically amortizable." — Bridge accounting is still required.
7. "Define $\Phi$ as the optimal remaining solving time, and then use $\Phi$ to prove the solving time." — Circular.

---

# 15. Formal Results of This Round

## 15.1 Polynomial ATC Proposition

Established:

$$
(\rho_A,\Phi_A,p,q,r)
$$

as a rigorous upper-bound certificate template for pathwise polynomiality.

## 15.2 Potential Is Meta, Not Magic

The potential function itself is not a solver, but merely a proof of the total cost of an existing computation.

## 15.3 Solver-Independence Correction

For the $P=NP$ side:

$$
\text{algorithm-specific potential is completely legal}.
$$

For the $P\neq NP$ side:

$$
\text{to deduce a lower bound from certificate failure, one must first prove certificate completeness}.
$$

## 15.4 Potential Certificate Completeness Trap

Certificate language:

$$
\text{Too weak}
\Rightarrow
\text{Misses }P,
$$

$$
\text{Too strong}
\Rightarrow
\text{Circular / Tautological / Risk of being undecidable}.
$$

## 15.5 Dual Certificate

Separated:

$$
\text{Progress / Ranking}
$$

and:

$$
\text{Amortized Resource Potential}
$$

---

# 16. Battle Results for Both Sides

## Team Equality

Obtained:

$$
\boxed{
\exists A,\rho_A,\Phi_A
\Rightarrow
\text{If ATC inequalities are satisfied, then pathwise polynomial}.
}
$$

They do not need to find a universal potential; they only need to establish a valid amortized proof for their own SAT algorithm.

## Team Inequality

Successfully prevented:

$$
\text{"A certain potential family fails"}
\Rightarrow
P\neq NP.
$$

And advanced the new battlefield to:

$$
\boxed{
\text{Tractability Certificate Completeness}
}
$$

---

# 17. Score of This Round

$$
P=NP:13
$$

$$
P\neq NP:13
$$

Both sides score one point again.

At this point, a "tie" is no longer a score, but a cosmological constant. (Wry smile)

The score is merely a game interface and holds no proof significance.

---

# 18. Gateway to Round 15: Tractability Proof System

Next round's formal research:

$$
\boxed{
\text{Can a polynomial tractability certificate language simultaneously possess soundness, broad completeness, and non-circularity?}
}
$$

Candidate questions:

1. Does there exist a restricted algorithm normal form such that polynomial runtime can be verified by a short certificate?
2. If the certificate system is sound but incomplete, what value does it still hold for $P\neq NP$?
3. If completeness for arbitrary Turing machines is required, does it directly collide with runtime-property undecidability?
4. Can we only require completeness for the "SAT quotient/bridge portfolio architecture" rather than for all programs?
5. Can we establish a solver architecture hierarchy:

$$
\mathcal A_0
\subset
\mathcal A_1
\subset
\cdots
$$

with layer-by-layer matching sound+complete tractability certificates?
6. If:

$$
\bigcup_i\mathcal A_i
$$

is sufficient to cover all polynomial SAT algorithms, is this coverage itself close to the original problem again?

---

# 19. Historical Dependencies

This round directly depends on:

1. `13_Round_13_Tractable_Closure_Stability_and_Polynomial_Chain_Explosion.md`
   - Stepwise / Pathwise Polynomiality;
   - Tractable Closure Stability;
   - Initial concept of ATC.

And connects back to:

2. `09_Round_09_Finding_the_Blossom_of_SAT_and_Quotient_Debt.md`
   - Quotient Debt.
3. `11_Round_11_Collapse_of_Co-preserved_Structures_and_Dynamic_Bridging.md`
   - Bridge Coordination Debt.
4. `12_Round_12_Interface_Language_Lattice_Schaefer_Criticality_and_Recursive_SAT.md`
   - Dynamic Tractable Closure Scheme.
5. Original P/NP Dynamic Rate Series
   - Distinction between meta-level discovery cost and object-level execution cost.

---

# 20. External Theoretical References

1. MIT OpenCourseWare, **6.046J Design and Analysis of Algorithms — Amortized Analysis / Potential Method**.
   - https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/

2. Martin Hofmann, Georg Moser, **Amortised Resource Analysis and Typed Polynomial Interpretations**, 2014.
   - https://arxiv.org/abs/1402.1922

3. Long Pham, Jan Hoffmann, **Typable Fragments of Polynomial Automatic Amortized Resource Analysis**, 2020.
   - https://arxiv.org/abs/2010.16353

4. David Gajser, **Verifying Time Complexity of Deterministic Turing Machines**, 2013.
   - https://arxiv.org/abs/1307.3648

5. Amir M. Ben-Amram, Chin Soon Lee, **Ranking Functions for Size-Change Termination II**, 2009.
   - https://arxiv.org/abs/0903.4382

6. Edward Zulkoski et al., **Relating Complexity-theoretic Parameters with SAT Solver Performance**, 2017.
   - https://arxiv.org/abs/1706.08611

---

## Ruling of This Round

$$
\boxed{
\text{The potential function is a very strong upper-bound weapon, but not a natural lower-bound weapon.}
}
$$

More precisely:

$$
\boxed{
\exists A+\exists\mathrm{ATC}_A
}
$$

can serve as a constructive certificate in the $P=NP$ route;

but:

$$
\boxed{
\neg\exists\mathrm{ATC}
}
$$

can only support $P\neq NP$ when the ATC certificate language has been proven complete for all $P$ algorithms.

Therefore, Round 14 did not yield $P=NP$ or $P\neq NP$, but it corrected "complexity potential" from a vague metaphor into a rigorous set of upper-bound proof tools, and pushed the true new battlefield to:

$$
\boxed{
\text{Tractability Proof-System Completeness}.
}
$$