# P/NP Debate Game Research Area | Round 03

## Algorithm-Trajectory Cuts and Causal Bottlenecks: Must Any Exact Solver Expose Distinguishable Bottlenecks?

**Round 03: Algorithm-Trajectory Cuts and Causal Bottlenecks**

- **Lead Researcher:** Neo.K (Chuan-Wei Hsu)
- **Collaborative Organization:** Aletheia
- **Institution:** EveMissLab (EveMiss Technology Co., Ltd.)
- **Date:** August 1, 2026
- **Version:** v1.0
- **Research Status:** Round 03 Dual-Hypothesis Rehearsal
- **Prerequisite Document(s):** `00`, `01`, `02`
- **Game Stance:** The Equality Team and Inequality Team continue to tear each other down; failed routes are archived as usual.
- **Document Standard:** Do not pass off local lower bounds as $P\neq NP$ proofs.

---

## Abstract

The "residual distinguishable load" from Round 02 formed a true semantic lower bound in state machines with fixed cuts and fixed information flows, but the Equality Team could escape via variable reordering, re-reading inputs, global summaries, dimension expansion, and representation switching. Round 03 therefore cancels externally specified variable cuts and directly studies the algorithm's own computational history:

$$
C_0(x)\to C_1(x)\to\cdots\to C_T(x).
$$

The Inequality Team proposes "trajectory cuts": if any exact solver must compress a large number of semantically distinct histories into a finite configuration at some point in time, then when the configuration capacity is insufficient, the unsaved differences can only be retrieved through future re-reading, recomputation, or other transformations. Thus, a "state-reconstruction" tradeoff may exist, rather than a simple space lower bound.

The Equality Team points out that the future of a standard Turing machine or RAM can still re-access the input; even if two inputs share the same working state at a certain moment, they do not have to share the same future, because they still carry different read-only inputs. Thus, a single time cut is not a true causal cross-section. If the entire input is also included in the cut state, there is at most $n$ bits of input information, and information counting alone is insufficient to deduce superpolynomial time.

This round thus yields an important negative result: **Shannon-type information quantities or configuration counts are insufficient to directly support $P\neq NP$; what truly needs to be lower-bounded might be the "structural transformation cost required to reconstruct a correct global decision from compressed representations and re-accessible inputs."**

This round upgrades the candidate core from "distinguishable information quantity" to "Causal Reconstruction Complexity" (CRC), but simultaneously confirms: if CRC is directly defined as the minimum solving time, it becomes circular. Round 04 will therefore pivot to finding local-global barriers that can independently characterize CRC.

---

# 1. Round 03 Opening: Returning the Cut to the Algorithm Itself

Round 02 defined the number of residual functions after partial assignment:

$$
N_{\mathrm{res}}(\varphi,S),
$$

and proved that in a state machine model where "once $S$ is read, there is no turning back":

$$
|Q_S|\ge N_{\mathrm{res}}(\varphi,S).
$$

The problem is that general algorithms do not have to follow the $S$ specified by the researcher.

So Round 03 changes to:

> Do not specify a route for the algorithm; directly observe the route it actually takes.

Let $A$ be any deterministic exact algorithm. For an input $x$ of length $n$, its execution trajectory is written as:

$$
\tau_A(x)
=
(C_0(x),C_1(x),\ldots,C_{T_A(x)}(x)).
$$

$C_t(x)$ is the complete machine configuration at time $t$, for example:

- Finite control state;
- Working memory;
- Work tape contents;
- Positions of all read/write heads;
- Intermediate data structures already built;
- Current program counter.

The read-only input itself is temporarily not considered part of the working configuration, as this is precisely the key to the subsequent offensive and defensive exchanges.

---

# 2. Inequality Team's First Move: Configuration Merging Must Pay a Price

For a fixed time $t$, define the configuration mapping:

$$
\kappa_t:x\mapsto C_t(x).
$$

If different inputs $x,y$ satisfy:

$$
C_t(x)=C_t(y),
$$

we say they are "configuration-merged" at time $t$.

The Inequality Team's intuition is as follows:

If $x,y$ still have essential differences for the subsequent correct decision, but the machine does not save the difference at that moment, then the difference has not truly disappeared; it can only:

1. Still exist in the re-accessible input;
2. Be encoded in some unmeasured external structure;
3. Be recomputed in the future;
4. Or the algorithm has actually found a higher-order summary that does not require this difference.

Therefore, a tentative conservation equation is proposed:

$$
\text{Unsaved Distinction}
\Rightarrow
\text{Future Reconstruction Obligation}.
$$

This rewrites the "complexity transfer" of Round 02 into a time-directional version.

---

# 3. Equality Team's First Heavy Blow: Same Configuration Does Not Mean Same Future

For a general Turing machine, even if:

$$
C_t(x)=C_t(y),
$$

if the input can still be re-read in the future, the machine can still take different paths when encountering $x$ and $y$.

Therefore:

$$
C_t(x)=C_t(y)
\not\Rightarrow
\text{future}_A(x)=\text{future}_A(y).
$$

This differs from finite automata. Characters read by a finite automaton usually leave the visible scope; a general Turing machine can turn back.

Thus, the Myhill–Nerode-style approach from Round 02 cannot be directly ported to arbitrary multi-tape Turing machines.

**The first failed result of this round:**

> "The working configuration at a certain moment has only polynomially many bits, so it can only distinguish polynomially many histories" is false. Polynomial bits can form exponentially many configurations; and even if the configurations are identical, the read-only input can still provide distinguishing information in the future.

---

# 4. Inequality Team's Upgrade: If State is Insufficient, Account for Re-reading and Recomputation

Since unsaved information can be retrieved from the input, put it into the cost ledger.

For a time cut $t$, let:

$$
S_t=|C_t|
$$

be the number of working state bits, and let:

$$
R_t
$$

be the input access, recomputation, and intermediate structure reconstruction costs required from $t$ to termination in order to regain the unsaved differences prior to the cut.

The Inequality Team proposes a "state-reconstruction tradeoff" candidate:

$$
\boxed{
\text{State}(t)+\text{Reconstruct}(t)
\ge
\text{RequiredDependency}(t)
}
$$

More abstractly:

$$
\mathsf{SR}_A(x,t)
=
S_t+R_t.
$$

If one can find a family of SAT instances such that for any exact algorithm there exists some $t$ satisfying:

$$
\mathsf{SR}_A(x,t)
\notin\operatorname{poly}(n),
$$

then this might lead to a general lower bound.

This is close in spirit to the classical time-space tradeoff: when space is insufficient, computation often requires more time to recompute; and vice versa. But currently, this is only a research direction, and a theorem applicable to SAT and general polynomial-time models has not yet been obtained.

---

# 5. Communication Complexity Version: Truly Cutting the Time Cut

To prevent "future re-reading of past inputs" from breaking the cut, one can artificially split the input into two parts:

$$
x=(a,b).
$$

Alice holds $a$, Bob holds $b$. If one segment of an algorithm's computation relies primarily on $a$ and another segment relies on $b$, one can attempt to simulate it as a communication protocol.

If correctly computing a function $f(a,b)$ requires massive communication, one can obtain lower bounds for certain computational models.

Rectangles, protocol trees, and distinguishable input pairs in deterministic communication complexity provide exactly this kind of tool.

But the Equality Team immediately points out:

1. SAT inputs do not have a naturally unique Alice/Bob cut;
2. The algorithm can interleave access to $a,b$ throughout its entire runtime;
3. Being hard for a certain communication decomposition does not mean it is hard for a general centralized algorithm;
4. Elevating a communication lower bound to a superpolynomial time lower bound for general Turing machines is itself a massive leap.

**Ruling:** Communication complexity provides a mature "cut lower bound language," but it remains a projected model for now.

---

# 6. Branching Program Version: Time-Space Tradeoffs Do Exist, But Are Still Insufficient

Branching programs can represent computation as a directed graph:

- Nodes represent states;
- Edges represent transitions based on input tests;
- Width reflects space;
- Length/size reflects time or total states.

Known research can prove non-trivial or even exponential branching program size lower bounds for certain functions and certain time restrictions, and can also obtain time-space tradeoffs.

This is crucial for the Inequality Team because it proves that "insufficient state necessitates paying more paths/time" is not purely philosophical intuition.

But the Equality Team still has a card to play:

> Being able to obtain lower bounds for certain functions, certain lengths, and certain branching program models does not mean one can obtain superpolynomial lower bounds for all polynomial-time algorithms for SAT.

Therefore, branching program results are conceptual evidence, not the endgame.

---

# 7. Unrolling Arbitrary Polynomial-Time Computation into Circuits

A very critical unified perspective also emerged in this round.

If a language $L\in P$, it can be computed by a polynomial-time uniform Boolean circuit family. Conversely, an appropriately uniform polynomial-size circuit family also characterizes polynomial-time computation.

Thus, any hypothetical polynomial-time algorithm for SAT can be time-unrolled into a family of polynomial-size uniform circuits:

$$
A
\leadsto
\{C_n\}_{n\ge1}.
$$

Consequently, "algorithm-trajectory cuts" can be rewritten as "causal cuts of the computation DAG."

Inputs are on the left side of the DAG, outputs on the right; all influences on the output must propagate along data dependency edges.

The Inequality Team therefore proposes:

> Does there exist a causal dependency measure independent of local circuit syntax that any polynomial-size circuit for SAT must violate?

The Equality Team replies:

> If you successfully prove that SAT has no polynomial-size general circuits, it is of course sufficient to deduce $P\neq NP$; but this itself is the famous and extremely difficult circuit lower bound problem. You have merely pushed the "trajectory bottleneck" to the true main battlefield.

**Ruling:** This is not a failure, but a successful localization: if general trajectory cuts are to accomplish their mission, they must ultimately possess at least the power to generate general circuit lower bounds.

---

# 8. The Most Important Reversal of This Round: Information Quantity is Insufficient

The Inequality Team originally wanted to naturally say: SAT has a massive search space, so the answer depends on a massive amount of information.

But the input length is only $n$, so the Shannon information upper bound of the entire input is also just:

$$
O(n)
$$

bit magnitude.

The output is even just:

$$
1
$$

bit.

Therefore, there is no simple information conservation equation that can say:

$$
\text{Exponential Candidates}
\Rightarrow
\text{Must Transmit Exponential Bits}.
$$

PARITY is already one of the simplest counterexamples: it depends on all $n$ bits, but can be processed with a one-bit rolling state.

So the real difficulty is not:

$$
\boxed{\text{How much information is needed?}}
$$

But more like:

$$
\boxed{\text{What structural transformations must this information undergo to obtain the correct answer?}}
$$

This is the true new turning point of Round 03.

---

# 9. Inequality Team's Third Upgrade: Causal Reconstruction Complexity CRC

Define a tentative concept:

$$
\operatorname{CRC}(f;x,t),
$$

representing that after time cut $t$, given:

1. The currently saved state;
2. The original input still allowed to be accessed;
3. Valid future computational operations;

the minimum "reconstruction structural cost" required to recover the global dependencies sufficient to exactly compute $f(x)$.

Note that CRC is deliberately not defined here as a simple bit quantity.

It might involve:

$$
\operatorname{CRC}
=
F(
\text{re-read},
\text{recompute},
\text{interaction},
\text{composition depth},
\text{representation growth}
).
$$

The Inequality Team hopes to ultimately obtain something like:

$$
\forall A\text{ exactly computing SAT},
\quad
\exists x,t,
\quad
\operatorname{CRC}_A(x,t)
\ge n^{\omega(1)}.
$$

---

# 10. Equality Team Catches a Circular Trap

If CRC is defined as:

$$
\operatorname{CRC}(f;x,t)
=
\min\{\text{time to compute }f(x)\text{ from the cut state}\},
$$

then proving CRC is superpolynomial is equivalent to re-proving the original problem.

Therefore, CRC is only useful if it can be characterized by more fundamental, independently computable, or lower-boundable mathematical objects.

For example, candidate sources could be:

- Combinatorial interaction structures;
- The gap between local consistency and global consistency;
- Proof complexity;
- Tensor/matrix factorization rank;
- Treewidth and elimination width;
- Structure of communication matrices;
- Extension complexity;
- Other cross-representation measures yet to be found.

Thus:

$$
\boxed{
\text{CRC is the name of a research goal, not a currently completed invariant.}
}
$$

---

# 11. Official Offensive and Defensive Exchanges of This Round

## 11.1 Inequality Team

The Inequality Team now no longer claims "exponential candidates = exponential information."

Instead:

> The difficulty of SAT might be that local information can be highly compressed, but to maintain exact global consistency for arbitrary constraint combinations, some structural reconstruction cost cannot be simultaneously compressed into polynomials across time, space, representation, and depth.

Candidate form:

$$
\mathfrak C_A
=
\left(
S,
T,
D,
R,
W,
P
\right),
$$

Where:

- $S$: State/Space;
- $T$: Transition time;
- $D$: Dependency depth;
- $R$: Reconstruction/Recomputation;
- $W$: Structural width;
- $P$: Representation precision.

Hoping to find an incompressible relationship among them simultaneously.

## 11.2 Equality Team

The Equality Team replies:

1. You have not proven these dimensions are complete;
2. A new representation might simultaneously reduce multiple existing dimensions;
3. The input of SAT is only $n$ bits; information theory itself poses no exponential barrier;
4. General circuits can highly reuse intermediate results;
5. As long as there exists a new mathematical representation that directly computes global consistency, all local bottleneck models might fail.

The Equality Team's strongest statement this round:

$$
\boxed{
\text{What you need to prove is not "information cannot be compressed," but "correct global relations cannot be computed at low cost."}
}
$$

And this statement is already very close to the core of $P/NP$, hence circularity must be avoided.

---

# 12. Reconnection with the Original Dynamic Rate Series

The original series separated "search-compute-verify" and emphasized that problem solvability evolves with knowledge and agent history; the actual cost of the same problem can shift significantly after the roles of Memorizer, Definer, and Cross-Base Space are activated.

This round refines the effect of the "Memorizer" into an important reminder:

$$
\text{Not saved}
\neq
\text{Information disappeared},
$$

because the algorithm can re-read or recompute in the future.

Therefore, the true dynamic cost should include:

$$
T_{\mathrm{reconstruct}}.
$$

Yielding the extended version:

$$
T_{\mathrm{total}}
=
T_{\mathrm{search}}
+
T_{\mathrm{formalize}}
+
T_{\mathrm{construct}}
+
T_{\mathrm{realize}}
+
T_{\mathrm{run}}
+
T_{\mathrm{reconstruct}}
+
T_{\mathrm{verify}}.
$$

This term is not a newly added complexity class for traditional $P/NP$, but an observational variable for analyzing internal complexity transfers within algorithms.

---

# 13. Routes Eliminated or Demoted This Round

The following propositions must not be used independently as $P\neq NP$ proofs in the future:

1. There are only finite/polynomial working states at a certain time point, so it is impossible to distinguish all inputs;
2. Two inputs have the same configuration at a certain moment, so they must be identical thereafter;
3. The candidate space is exponentially large, so exponential information must be transmitted;
4. SAT depends on all inputs, so it requires at least exponential memory;
5. A certain communication cut is hard, so centralized algorithms must also be hard;
6. A certain time-space tradeoff exists, so SAT must be superpolynomial;
7. Directly defining "reconstruction complexity" as the optimal remaining runtime, and then using it to prove a lower bound.

---

# 14. Weapons Retained This Round

## 14.1 Trajectory Observation Remains Valuable

Any algorithm generates a computational history; history can be unrolled into branching programs, computation DAGs, or uniform circuits. Therefore, "algorithm trajectory" is not a fictional object.

## 14.2 Time-Space-Recomputation Tradeoffs Do Exist

Classical branching programs and time-space tradeoff results provide restricted but real examples, proving that recomputation can compensate for space, and lower bounds can sometimes capture this tradeoff.

## 14.3 Information Quantity and Computational Structure Must Be Separated

$$
\text{Information Amount}
\neq
\text{Computational Transformation Cost}.
$$

This is the most important methodological correction of this round.

## 14.4 General Trajectory Lower Bounds Will Encounter General Circuit Lower Bounds

If trajectory cuts can truly form superpolynomial barriers against all polynomial-time algorithms, they must possess at least the power to rule out polynomial-size uniform circuits.

This makes the research direction more honest and more focused.

---

# 15. Barrier Review

## 15.1 Relativization

Pure black-box arguments that "the algorithm can only obtain certain input information each time" are prone to relativization, hence high risk.

## 15.2 Natural Proofs

If the new "causal invariant" holds for a large number of functions, is efficiently recognizable, and can rule out small general circuits, the natural proofs barrier must be checked.

## 15.3 Algebrization

If CRC is ultimately transformed into rank, matrix, polynomial, or tensor measures, the algebrization barrier must still be specifically checked.

## 15.4 Model Bait-and-Switch

Local results from communication, branching programs, formulas, analytic proofs, etc., must continuously specify their models and must not be directly elevated to general Turing machine conclusions.

---

# 16. Ruling of This Round

The Inequality Team successfully upgraded "fixed variable cuts" to "the algorithm's own trajectory," but quickly ran into two problems:

$$
\text{Inputs are re-readable}
$$

and:

$$
\text{Information quantity is only }O(n).
$$

The Equality Team thus successfully shattered the "simple information bottleneck proof."

But the Inequality Team obtained a new research object:

$$
\boxed{\operatorname{CRC}:\text{Causal Reconstruction Complexity}}
$$

And confirmed that the next step can no longer just count states or bits, but must study:

$$
\boxed{
\text{After local compression, what unavoidable structural transformations are actually required to recover global correctness?}
}
$$

Score for this round:

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

Reason: The Equality Team shattered the simple information bottleneck; the Inequality Team successfully advanced the research from information quantity to computational structural cost.

The score remains merely a game interface, not mathematical evidence.

---

# 17. Entrance to Round 04

## Local-Global Barrier: Does SAT's Global Consistency Possess a Core That Cannot Be Reconstructed at Low Cost?

The next round will no longer ask "how much information can a cut save," but will ask:

$$
\boxed{
\text{How are massive local constraints combined into a global existential decision?}
}
$$

The Inequality Team will attempt to establish:

$$
\text{Local Consistency}
\not\Rightarrow
\text{Global Witness}
$$

the reconstruction cost generated by [the above].

The Equality Team will argue: perhaps there exists some unknown algebraic/geometric/topological summary that can directly compress global consistency into polynomial evaluation.

This round is expected to study:

- The gap between local consistency and global satisfiability;
- Constraint interaction graphs and elimination width;
- Local-global phenomena in proof complexity;
- Whether a "global coupling load" independent of specific representations can be established.

---

# 18. Data History Dependencies

This round inherits the following perspectives from the original series:

1. *Dynamic Rate Theory 2.9*: Search, execution, and verification must be decoupled; once knowledge is formed, search can be converted into invocation.
2. *Dynamic Rate Theory and the Structural Continuous Model of the P vs. NP Problem 2.0*: Solvability evolves with agents and time, but this does not replace traditional static classes.
3. *The Seven Phases of the Calculator*: Changes in the Memorizer, Definer, and Base Space shift actual costs; memory/precomputation cannot be unconditionally treated as free resources.
4. `00`: Cognitive achievements must undergo formalization, mathematical construction, base realization, and state transition before becoming repeatable algorithms.
5. `01`: The common arena is the existential quantifier compressor.
6. `02`: Fixed-cut residual distinguishability is a local lower bound, but can be escaped by general algorithms.

---

# 19. External Theoretical References

1. Anup Rao and Amir Yehudayoff, *Communication Complexity and Applications*, Cambridge University Press, 2020.
   - Deterministic communication protocols, rectangles, and communication lower bounds provide a true cut-style language.
2. Paul Beame, T. S. Jayram, Michael Saks, “Time–Space Tradeoffs for Branching Programs,” *Journal of Computer and System Sciences*, 2001.
   - Demonstrates non-trivial time-space tradeoffs in general branching programs and exponential size lower bounds under specific lengths.
3. Andrew C.-C. Yao, “Near-Optimal Time-Space Tradeoff for Element Distinctness,” *SIAM Journal on Computing*, 1994.
   - Provides a classical example of time-space tradeoffs.
4. Walter L. Ruzzo, “On Uniform Circuit Complexity,” *Journal of Computer and System Sciences*, 1981.
   - Background reference for the relationship between uniform circuits and machine models.

---

## Round 03 One-Sentence Record

> **We originally wanted to prove that "information cannot pass through"; it turns out that information can actually be retrieved by turning back. What truly needs to be proven might be: even if the information is always there, recombining it into an exact global answer still requires paying some incompressible structural cost.**