# P/NP Debate Game Research Area | Round 18

## Diagonal-Slice Compression and Sparsity Upward Separation Trap: Self-Reference Does Not Compress Proofs for Free

**Diagonal-Slice Compression, Sparsity Upward Separation, and the Failure of Free Self-Reference Compression**

- **Lead Researcher:** Neo.K
- **Collaborative Organization:** Aletheia
- **Date:** 2026-08-01
- **Version:** v1.0
- **Prerequisite:** `17_Round_17_Unified_Computation_Certificate_Compression_and_Universalization_Jump.md`
- **Research Status:** Dual-hypothesis rehearsal; non-formal P/NP proof

---

## Abstract

Round 17 split universal certificate compression into three layers: fixed-machine, universal-indexed, and diagonal-slice. The universal-indexed version is too strong because Universal Clocked Polynomial Evaluation (UCPE) jumps to EXPTIME-complete; the only path that might still leave a gap is the diagonal slice: seeking a short rejection certificate of fixed degree solely for the $i$-th clocked polynomial machine $C_i$ and its designated diagonal input $x_i$.

After fully exploring this path in this round, we discovered a new phenomenon of "reverse difficulty escalation."

If, to keep the diagonalization clean, we allocate only a small number of designated inputs (or even just one) to each $C_i$, and arrange these inputs at sparse lengths, then the diagonal language

$$
D
=
\{x_i:C_i(x_i)=0\}
$$

naturally becomes a sparse / tally-like language. If at this point we can also prove via a Uniform Diagonal Rejection Certificate (UDRC) that:

$$
D\in NP,
$$

while the diagonal construction simultaneously guarantees:

$$
D\notin P,
$$

then what we obtain is not an ordinary $NP\setminus P$ witness, but rather:

$$
\boxed{
\text{sparse }D\in NP\setminus P.
}
$$

This appears simpler, but is actually stronger. The upward-separation result by Hartmanis–Immerman–Sewelson shows that: a sparse set exists in $NP-P$ if and only if the single-exponential time classes, which their paper refers to as EXPTIME and NEXPTIME, are not equal. The paper explicitly defines:

$$
EXPTIME=\bigcup_{c>0}TIME(2^{cn}),
$$

$$
NEXPTIME=\bigcup_{c>0}NTIME(2^{cn}),
$$

which in modern common notation is closer to $E$ and $NE$. Therefore, if we truly make the diagonal slice a sparse $NP\setminus P$, we don't just get $P\neq NP$; we simultaneously obtain a higher-order deterministic/nondeterministic exponential-time separation.

This round names this:

$$
\boxed{
\mathrm{SUST}
=
\text{Sparsity Upward-Separation Trap}
}
$$

——**Making the diagonalization too sparse does not simplify the problem; instead, it may upgrade what needs to be proven.**

This also directly answers the self-reference question left from Round 17. Kleene recursion theorem / self-reference techniques allow a program to obtain or act upon its own description, thereby creating a fixed point; but fixed-point existence does not automatically provide:

$$
\text{short proof},
\qquad
\text{short computation},
\qquad
\text{fixed-degree certificate}.
$$

Therefore:

$$
\boxed{
\text{self-reference is an addressing mechanism, not a compression theorem.}
}
$$

This round names this false intuition the **Self-Reference Compression Fallacy (SRCF)**.

Then a second pincer attack emerges. If, to avoid the sparse-set upward separation barrier, we make the diagonal set "dense": allocating large blocks instead of a single point per machine, or making the machine index part of the general input, then we gradually return to the Universalization Complexity Jump of Round 17: once the machine index, clock exponent, and input are all variable, unified evaluation will once again carry an unbounded exponent and move toward EXPTIME-class universal bounded-computation problems.

Thus, we arrive at the most important new structure of this round:

$$
\boxed{
\mathrm{DUS}
=
\text{Density--Uniformity Squeeze}
}
$$

Its two ends are:

$$
\text{Highly sparse}
\Longrightarrow
\text{upward-separation barrier},
$$

$$
\text{Sufficiently dense / universal}
\Longrightarrow
\text{uniform-exponent / universalization barrier}.
$$

Therefore, Round 19 will no longer expect "point-by-point diagonalization" to fall directly into NP, but will instead play with **Block Diagonalization / Delayed Diagonalization**: can we give each polynomial machine a controllable input block, using delay, staging, and density management to simultaneously avoid the sparse barrier and the universal exponent barrier? This will perfectly intersect with Ladner-style delayed diagonalization, density control, and padding techniques.

---

# 1. The Narrowest Gap Left from Round 17

Round 17 has already ruled out the overly strong wish:

$$
\forall M,x,k,
$$

there exists a clocked-computation certificate of fixed $n^K$ size.

That would put UCPE into NP, thereby producing extremely strong consequences via EXPTIME-completeness.

Thus, it only leaves:

$$
\boxed{
(C_i,x_i)
}
$$

this special diagonal slice.

Let:

$$
C_1,C_2,C_3,\ldots
$$

be an effective enumeration of all clocked polynomial-time deterministic machines.

Assign a designated input to each $i$:

$$
x_i.
$$

Define:

$$
\boxed{
D(x_i)=1-C_i(x_i).
}
$$

As long as indexing / duplicate handling is done correctly, we can ensure:

$$
\forall i,
\qquad
D\neq L(C_i),
$$

hence:

$$
D\notin P.
$$

The only remaining question is:

$$
\boxed{
D\stackrel{?}{\in}NP.
}
$$

---

# 2. UDRC: What We Really Need is a Rejection Certificate

By definition:

$$
x_i\in D
\iff
C_i(x_i)=0.
$$

So the NP witness must prove:

$$
\boxed{
\text{deterministic }C_i\text{ rejects on }x_i.
}
$$

Round 17 named this:

$$
\mathrm{UDRC}
=
\text{Uniform Diagonal Rejection Certificate}.
$$

The ideal version requires the existence of a fixed verifier $V$ and a fixed constant $K$:

$$
x_i\in D
\iff
\exists \pi,
\quad
|\pi|\le |x_i|^K,
$$

and:

$$
V(x_i,\pi)=1
$$

can be completed within:

$$
|x_i|^K
$$

or another fixed polynomial bound.

If this exists, we have:

$$
D\in NP.
$$

Combined with diagonalization:

$$
D\notin P,
$$

we get:

$$
P\neq NP.
$$

So UDRC looks like an extremely narrow but legitimate line of attack.

---

# 3. First New Discovery: Diagonal Slices Naturally Become Sparse

The cleanest diagonal constructions usually deliberately avoid having designated inputs interfere with each other.

For example, choosing:

$$
|x_1|<|x_2|<|x_3|<\cdots
$$

or even making:

$$
|x_{i+1}|
$$

much larger than all previous lengths.

If each $i$ corresponds to only one $x_i$, then up to length $n$, the number of YES candidates in $D$ is at most equal to the number of diagonal indices that have been assigned.

If arranged such that:

$$
|D\cap\{0,1\}^{\le n}|\le n^c
$$

holds for some fixed $c$, then:

$$
\boxed{D\text{ is a sparse language}.}
$$

More radically, if we only use:

$$
x_i=1^{m_i},
$$

we even get a tally-like diagonal set.

Intuitively, this seems good:

> Fewer instances should make it easier to prove membership, right?

But complexity theory gives a very counterintuitive answer here.

---

# 4. Hartmanis–Immerman–Sewelson: Sparse NP-P Separates Upward

Hartmanis, Immerman, and Sewelson studied sparse sets in $NP-P$ and obtained an upward-separation result.

Their core theorem is written as:

$$
\boxed{
\exists\text{ sparse }S\in NP-P
\iff
EXPTIME\neq NEXPTIME
}
$$

But we must be very careful with notation here.

The paper explicitly defines:

$$
EXPTIME
=
\bigcup_{c>0}TIME(2^{cn}),
$$

$$
NEXPTIME
=
\bigcup_{c>0}NTIME(2^{cn}).
$$

This is close to the notation used today where:

$$
E=DTIME(2^{O(n)}),
$$

$$
NE=NTIME(2^{O(n)})
$$

are used for single-exponential classes; modern common EXP/NEXP usually allow $2^{n^{O(1)}}$.

So to avoid notational pollution, this series temporarily denotes the single-exponential separation in that paper as:

$$
\boxed{
E_{\mathrm{linexp}}
\neq
NE_{\mathrm{linexp}}.
}
$$

The key is not the name, but the structure:

$$
\boxed{
\text{sparse }NP\setminus P
\Longleftrightarrow
\text{higher-order deterministic/nondeterministic time separation}.
}
$$

The original authors even directly pointed out:

> If we separate P and NP using a sparse set, we simultaneously separate higher exponential classes; this might be harder than just proving $P\neq NP$.

This almost collides head-on with our current diagonal slice.

---

# 5. Sparsity Upward-Separation Trap (SUST)

Therefore, this round defines:

$$
\boxed{
\mathrm{SUST}
=
\text{Sparsity Upward-Separation Trap}.
}
$$

If the diagonal construction satisfies:

1. Each $C_i$ is allocated only $O(1)$ designated inputs;
2. Designated lengths grow sparsely;
3. Consequently, $D$ is sparse;
4. UDRC also proves $D\in NP$;
5. Diagonalization proves $D\notin P$;

Then what we actually obtain is:

$$
\boxed{
\text{sparse }D\in NP-P.
}
$$

By upward separation:

$$
\boxed{
E_{\mathrm{linexp}}\neq NE_{\mathrm{linexp}}.
}
$$

And this, of course, implies:

$$
P\neq NP.
$$

So:

$$
\boxed{
\text{Making the diagonal slice too thin does not lower the proof threshold; it may raise it.}
}
$$

This is the most important new result of Round 18.

---

# 6. Second Alarm: Mahaney Sparse Completeness Trap

Another related classic result is Mahaney's theorem.

If there exists a sparse language $S$ that is NP-complete under polynomial-time many-one reductions, then:

$$
\boxed{P=NP.}
$$

Therefore, if we construct a sparse diagonal set $D$, we can no longer naively demand:

$$
D\text{ is simultaneously NP-complete}
$$

as the standard hard witness for the Not-Equal Team.

Because:

$$
\text{sparse}+\text{NP-complete}
$$

would instead push the game toward:

$$
P=NP.
$$

But we must remain precise here:

To prove $P\neq NP$, we only need:

$$
D\in NP-P,
$$

we **do not need** $D$ to be NP-hard or NP-complete.

So Mahaney's theorem does not kill the diagonal-slice route; it merely tells us:

$$
\boxed{
\text{A sparse separation witness and a standard NP-complete hard core are different strategies.}
}
$$

---

# 7. What Can Self-Reference Really Do?

Round 17 left another temptation:

> If $x_i$, $C_i$, and the proof are all tied together via self-reference, can we compress the rejection proof by relying on "it talking about itself" without full simulation?

Kleene recursion theorem-style results indeed provide:

$$
\boxed{
\text{A program can effectively obtain its own description / form a computable fixed point}.
}
$$

That is, given an appropriate computable transformation:

$$
F,
$$

one can construct a program index $e$ such that its behavior forms a fixed-point relationship with:

$$
F(e)
$$

But the conclusion of this theorem is:

$$
\boxed{
\text{extensional fixed-point existence}.
}
$$

It does not say:

$$
T_e(n)=O(n^K),
$$

it does not say:

$$
\text{rejection has a short proof of size }n^K,
$$

nor does it say:

$$
\text{the fixed point can be quickly verified by an NP verifier}.
$$

So:

$$
\boxed{
\text{Self-reference provides the ability to "point to oneself",}
}
$$

but does not automatically provide:

$$
\boxed{
\text{the ability to "quickly know what one ultimately did".}
}
$$

---

# 8. Self-Reference Compression Fallacy (SRCF)

This round therefore formally establishes a false-proof prevention rule:

$$
\boxed{
\mathrm{SRCF}
=
\text{Self-Reference Compression Fallacy}.
}
$$

Erroneous reasoning:

$$
\text{statement / machine can refer to itself}
$$

$$
\Downarrow
$$

$$
\text{its semantic truth therefore has a short certificate}.
$$

This does not hold.

Self-reference and proof compression are two different dimensions:

### Self-reference cost

$$
C_{\mathrm{ref}}
$$

Controls:

- How to obtain its own encoding;
- How to establish a fixed point;
- How to specify the diagonal target.

### Semantic certification cost

$$
C_{\mathrm{cert}}
$$

Controls:

- How to prove the machine accepts/rejects;
- How long the proof is;
- How fast the verifier is;
- What the soundness model is.

Generally, we do not have:

$$
C_{\mathrm{ref}}\ll n^K
\Rightarrow
C_{\mathrm{cert}}\ll n^K.
$$

---

# 9. The Equality Team's Counterattack: Then I Won't Make the Diagonal Set Sparse

Upon discovering SUST, the Equality Team immediately said:

> Fine, then I won't do "one machine, one point". I'll give each $C_i$ an entire block!

For example:

$$
B_i
=\{\langle i,y\rangle:|y|\in I_i\}.
$$

And then define some kind of block diagonalization:

$$
D_B(\langle i,y\rangle)
$$

to reverse/challenge $C_i$ within block $B_i$.

This can increase density.

If each length has a large number of designated strings, it might no longer be sparse.

This seemingly bypasses the Hartmanis–Immerman–Sewelson upward-separation trap.

But...

---

# 10. As Density Increases, Uniformity Returns

Once the general input takes the form:

$$
\langle i,y\rangle,
$$

the verifier must handle any clocked machine specified by:

$$
i
$$

which is:

$$
C_i,
$$

and the polynomial exponent of $C_i$:

$$
k_i
$$

may be unbounded.

If the membership definition of the block language directly relies on:

$$
C_i(\langle i,y\rangle),
$$

then we encounter again:

$$
\boxed{
\text{Uniform Exponent Barrier}.
}
$$

When:

$$
i,k_i,y
$$

all become part of the unified input domain, the problem starts moving from:

$$
\text{fixed slice}
$$

toward:

$$
\text{universal evaluation}
$$

This is exactly Round 17's:

$$
\mathrm{UCJ}
=
\text{Universalization Complexity Jump}.
$$

So:

$$
\boxed{
\text{Sparsification reduces uniformity but triggers upward separation;}
}
$$

$$
\boxed{
\text{Densification avoids sparsity but raises uniformity again.}
}
$$

---

# 11. Density--Uniformity Squeeze (DUS)

This round formally names this two-way pincer attack:

$$
\boxed{
\mathrm{DUS}
=
\text{Density--Uniformity Squeeze}.
}
$$

Roughly represented as:

$$
\begin{array}{ccc}
\text{Sparse diagonal slice}
&\longrightarrow&
\text{SUST / higher-class separation}
\\
&&
\\
\text{Dense indexed diagonal family}
&\longrightarrow&
\text{UEB / UCJ / universal evaluation}
\end{array}
$$

This is not a formal complexity dichotomy theorem.

Currently, it can only be viewed as:

$$
\boxed{
\text{A double-ended pressure map in the research design space.}
}
$$

If in the future "all diagonal constructions" can be formalized into an analyzable family, it might be upgraded to a true theorem.

---

# 12. Why Are Sparse Set Results Particularly Relevant to Us?

The original motivation of Hartmanis–Immerman–Sewelson is inherently very close to the problem of this round in our series.

They studied:

> If there really are hard individual instances in NP-P, can we concentrate them into a low-density set?

The results showed that the existence of such "low-density but still hard" sets is deeply coupled with the separation of higher complexity classes.

Our current diagonal slice is doing exactly:

$$
\boxed{
\text{Picking an individual counterexample for each polynomial machine.}
}
$$

This is naturally the set-ification of:

$$
\text{individual hard instances}
$$

So sparse-set theory is not a side branch, but very accurately hits the structure of this diagonal route.

---

# 13. Re-evaluating DSCC from Round 17

Round 17 proposed:

$$
\mathrm{DSCC}
=
\text{Diagonal-Slice Certificate Compression}.
$$

This round splits it into two types.

## 13.1 Sparse-DSCC

Only compresses:

$$
(C_i,x_i)
$$

a small number of designated diagonal points.

If successful and $D\notin P$:

$$
\boxed{
\text{sparse }NP-P
}
$$

triggers SUST.

## 13.2 Dense-DSCC

Expands to a large number of:

$$
(C_i,x_{i,j})
$$

or indexed blocks.

Can avoid sparsity, but the machine index / exponent more fully enters the uniform input, gradually triggering:

$$
\boxed{
\mathrm{UEB}+\mathrm{UCJ}.
}
$$

So DSCC has not disappeared, but has been split into two different high-cost paths.

---

# 14. What Can Proof Complexity Do Here?

Suppose we build a propositional formula for each diagonal pair:

$$
\Theta_i
=
\text{"}C_i(x_i)\text{ rejects"}.
$$

If there exists a proof system $\mathcal P$ such that every true $\Theta_i$ has:

$$
|\pi_i|\le |x_i|^K,
$$

and proof checking is polynomial, it might form a UDRC.

But we must be very careful:

Cook–Reckhow's polynomially bounded proof-system theorem states:

$$
\boxed{
\text{All propositional tautologies have polynomial-size proofs}
\iff
NP=coNP.
}
$$

We are now only asking for a very special family:

$$
\{\Theta_i\}.
$$

So:

$$
\boxed{
\text{The diagonal family having short proofs}
\not\Rightarrow
NP=coNP.
}
$$

Conversely:

$$
\boxed{
\text{A proof system having a long lower bound for }\Theta_i
\not\Rightarrow
\text{all proof systems are long}.
}
$$

Therefore, proof complexity remains a candidate mechanism here, not an automatic separation.

---

# 15. Third New Concept: Family-Selective Proof Compression

This round names "compressing only a special diagonal family" as:

$$
\boxed{
\mathrm{FSPC}
=
\text{Family-Selective Proof Compression}.
}
$$

It is different from universal proof compression.

Universal:

$$
\forall\varphi\in TAUT,
\quad
\exists\pi,
|\pi|\le poly(|\varphi|).
$$

Family-selective:

$$
\forall i,
\quad
\Theta_i\in TAUT
\Rightarrow
\exists\pi_i,
|\pi_i|\le |x_i|^K.
$$

This requirement is much weaker.

But if the family itself is connected by the diagonal construction to:

$$
D\in NP-P,
$$

then weak proof compression might still have very strong complexity consequences.

This is another counterintuitive point of this round:

$$
\boxed{
\text{A narrow coverage of a proof system does not mean its complexity consequence is necessarily weak.}
}
$$

It depends on how that family is selected.

---

# 16. Quantifier Rewriting of Diagonalization and Sparsity

Generally, $P\neq NP$ requires:

$$
\exists L\in NP
\quad
\forall C_i\in P,
\quad
L\neq L(C_i).
$$

What the diagonal slice does is:

$$
\forall i,
\quad
\exists x_i,
\quad
L(x_i)\neq C_i(x_i).
$$

If each $i$ consumes only one $x_i$, the semantic universal attack:

$$
\forall i
$$

is compressed into data density as:

$$
O(1)\text{ witness point per machine}.
$$

This is exactly why the sparse structure naturally appears.

In other words:

$$
\boxed{
\text{Diagonalization witnesses universal separation using very few instances,}
}
$$

and upward-separation theory tells us:

$$
\boxed{
\text{this kind of "low-density universal witness" is inherently very strong.}
}
$$

---

# 17. Response to the Initial "Mathematical Function Compression Search" Proposition

Going all the way back to the initial video.

We initially asked:

> With many candidates / many steps, is it possible to directly compress them through an elegant mathematical function?

By Round 18, the answer has become more mature:

### Compressions that can happen

- XOR can be linearized;
- matching can undergo blossom contraction;
- a proof can be shorter than a trace;
- self-reference can connect a description to itself;
- sparse encoding can concentrate individual instances.

### But for every kind of compression, we must ask

$$
\boxed{
\text{Which dimension does it compress?}
}
$$

For example, self-reference compresses:

$$
\text{description addressing},
$$

which is not equal to compressing:

$$
\text{semantic verification complexity}.
$$

Sparsity compresses:

$$
\text{instance density},
$$

but may push the structural consequence to higher complexity classes.

This once again supports the core methodology of the entire series:

$$
\boxed{
\text{Do not just ask "has the cost decreased?", but ask "where did which kind of cost go?".}
}
$$

---

# 18. Erroneous Routes Eliminated in This Round

The following inferences are formally blacklisted in this round.

## Error 1

$$
\text{Diagonal set is very sparse}
\Rightarrow
\text{easier to prove it is in NP}.
$$

Does not hold. Sparse $NP-P$ inherently has higher-order separation consequences.

---

## Error 2

$$
\text{self-reference}
\Rightarrow
\text{short rejection certificate}.
$$

Does not hold. A fixed point is not a proof-compression theorem.

---

## Error 3

$$
\text{Making the diagonal set dense}
\Rightarrow
\text{automatically avoids the exponent barrier}.
$$

Does not hold. Increasing density usually requires more uniform indexed evaluation.

---

## Error 4

$$
\text{sparse }D\in NP-P
\Rightarrow
D\text{ can conveniently be made NP-complete}.
$$

Cannot be done casually; Mahaney's theorem states that a sparse NP-complete set leads to $P=NP$.

---

## Error 5

$$
\text{A proof system is hard for diagonal formulas}
\Rightarrow
D\notin NP.
$$

Still merely a proof-system lower bound.

---

# 19. Formal Results of This Round

## 19.1 Sparsity Upward-Separation Trap (SUST)

If the diagonal slice is arranged to be sparse, and successfully yields:

$$
D\in NP-P,
$$

it will trigger a higher-order deterministic/nondeterministic time separation.

So a sparse diagonal separation is not a "weaker version of P/NP".

---

## 19.2 Self-Reference Compression Fallacy (SRCF)

Kleene-style self-reference:

$$
\text{fixed-point / self-description}
$$

does not automatically derive:

$$
\text{fixed-degree proof compression}.
$$

---

## 19.3 Density--Uniformity Squeeze (DUS)

Currently observed:

$$
\text{sparse}
\rightarrow
\text{upward-separation pressure},
$$

$$
\text{dense/universal}
\rightarrow
\text{uniformization pressure}.
$$

This is currently a research design map, rather than a proven general dichotomy.

---

## 19.4 Family-Selective Proof Compression (FSPC)

What we really need is not short proofs for all tautologies, but only short proofs for the special diagonal rejection family.

This avoids directly equating to $NP=coNP$, but if this family corresponds to a sparse $NP-P$ witness, its consequence might still be very strong.

---

# 20. Battle Results of Both Sides

## $P\neq NP$ Team

This round obtained very beautiful external support:

$$
\boxed{
\text{If a sparse diagonal witness succeeds, it will even upward-separate exponential classes.}
}
$$

Therefore, "one machine, one counterexample" is not a simple version of separation.

### New Weapons

$$
\mathrm{SUST}
$$

$$
\mathrm{DUS}
$$

---

## $P=NP$ Team

Successfully prevented the Not-Equal Team from treating self-reference as a free proof compressor, and forced the opponent to admit:

$$
\boxed{
\text{To avoid the sparse barrier, one must increase density / block structure,}
}
$$

which reopens the space for representation, bridges, and compression.

That is: the sparse diagonal route being stuck does not mean all non-sparse constructions are stuck.

### New Weapons

$$
\text{Block / Dense Escape}
$$

---

# 21. Current Score

$$
P=NP:17
$$

$$
P\neq NP:17
$$

……

It is now very hard to explain this as a "coincidence".

Perhaps this research area has secretly implemented a conservation constraint of:

$$
\boxed{
\Delta \text{score}=0
}
$$

 (wry smile)

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

---

# 22. Entrance to Round 19: Block / Delayed Diagonalization

The next round will no longer adopt:

$$
\text{one machine}\leftrightarrow\text{one diagonal point}.
$$

Instead, it will consider:

$$
\boxed{
\text{one machine}\leftrightarrow\text{one controlled block / stage}.
}
$$

Studying:

$$
B_1,B_2,B_3,\ldots
$$

where each block corresponds to one or a set of polynomial machines.

Core questions:

1. Can we use block density to avoid sparse-set upward separation?
2. Can we use delayed diagonalization to avoid paying the unbounded $k_i$ at the same moment?
3. Can we make the membership verifier only need to check fixed-degree information of the "current stage"?
4. Why can Ladner's delayed diagonalization create an NP-intermediate language assuming $P\neq NP$, but cannot unconditionally prove $P\neq NP$ in reverse?
5. Density schedule:

$$
d(n)
$$

Can it become a buffer layer between the exponent schedule:

$$
k_i
$$

and the NP witness bound:

$$
n^K
$$

?
6. Hartmanis–Immerman–Sewelson have already pointed out: if Ladner-style delayed diagonalization wants to produce a sparse $NP-P$, it will still require a higher exponential separation. Then, does a non-sparse block construction offer another exploitable window?

Next round tentative title:

$$
\boxed{
\text{Block Diagonalization and Delayed-Density Game}
}
$$

---

# 23. External Theoretical References

1. J. Hartmanis, N. Immerman, V. Sewelson, **Sparse Sets in NP-P: EXPTIME versus NEXPTIME**, *Information and Control* 65 (1985), 158–181.
   - Core: A sparse set exists in $NP-P$ iff EXPTIME $\neq$ NEXPTIME as defined in the paper; the paper also points out that if P/NP is separated by a sparse set, a higher-order separation will simultaneously be obtained.
   - Note: EXPTIME in the paper is defined as $\bigcup_{c>0}TIME(2^{cn})$, which differs from the modern common EXP notation.

2. Stephen R. Mahaney, **Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis**, *Journal of Computer and System Sciences* 25 (1982), 130–143.
   - Core: If there exists a sparse NP-complete set (polynomial-time many-one), then $P=NP$.

3. Stephen A. Cook, Robert A. Reckhow, propositional proof systems.
   - polynomially bounded propositional proof system iff $NP=coNP$; this round only uses it to distinguish universal proof compression from family-selective proof compression.

4. Kleene recursion theorem / computability fixed-point literature.
   - self-reference can establish computable fixed points, but the theorem itself does not give runtime / proof-length compression.

5. Ladner delayed diagonalization.
   - As the main comparison target for the block/stage diagonalization in Round 19.

---

## Round Verdict

The diagonal-slice certificate compression left from Round 17 did not form a free loophole.

If the slice is made extremely sparse:

$$
\boxed{
\text{UDRC}+\text{diagonalization}
\Rightarrow
\text{sparse }NP-P,
}
$$

and sparse $NP-P$ inherently connects to a higher-order exponential-time separation.

If the slice is made denser to escape sparsity:

$$
\boxed{
\text{the uniformity of the machine index / exponent re-enters the picture.}
}
$$

And self-reference:

$$
\boxed{
\text{can help us "point to ourselves", but cannot help us "prove ourselves" for free.}
}
$$

So what Round 18 truly obtained is not an answer, but a sharper design constraint than the previous round:

$$
\boxed{
\text{The P/NP diagonal route seems to be squeezed between density and uniformity.}
}
$$

Round 19 will formally attempt to slip through this squeeze using block / delayed diagonalization.