diff d214c92..b1f9bc4 variable_dim_weisfeiler_leman_v2.txt
diff --git a/variable_dim_weisfeiler_leman_v2.txt b/variable_dim_weisfeiler_leman_v2.txt
index 8de1a8f..496bd3f 100644
--- a/variable_dim_weisfeiler_leman_v2.txt
+++ b/variable_dim_weisfeiler_leman_v2.txt
@@ -19,44 +19,6 @@ maximum degree at most three.
-0. THE SHAPE OF THE PROOF.
-
-There is one main theorem and one long reduction. The reduction turns an
-arbitrary exponential-time computation into a pair of polynomial-size
-graphs. Everything is built so that a particular two-player game on the
-pair has a winning strategy exactly when the computation rejects.
-
-The proof is a chain of six links. Each link is a self-contained lemma or
-proposition with a complete proof, and each link has a one-sentence
-statement of what it buys:
-
- Link 1 (Section 3). Every exponential-time computation on an input of
- length m becomes a polynomial-size "product circuit" whose accepting
- tests are false exactly when the input should be accepted.
-
- Link 2 (Section 4). Every such circuit becomes a system of constraints
- on small sets of bits ("scalar-image consistency"), solvable exactly
- when every test is false.
-
- Link 3 (Section 5). Every consistent system becomes a supply of
- compatible "affine offsets" on small sets of local blocks, with an
- exact extension property: any allowed choice on a small set extends
- when one more block is added.
-
- Link 4 (Section 6). The offsets become winning moves in the game, and
- conversely the game recovers the constraints. This is the game transfer.
-
- Link 5 (Section 7). The same block data is realized by connected graphs
- of maximum degree three, with the same game and decoding properties.
-
- Link 6 (Section 8). All objects have polynomial size and are produced
- in polynomial time, which completes the reduction and the theorem.
-
-If you only want the shape of the argument, read Section 1 and the
-statement of each of the six links. If you want the proof, read straight
-through. Every claim used later is proved before it is used.
-
-
1. WHAT IS PROVED, AND WHY IT IS SURPRISING.
1.1 The two problems.
@@ -120,128 +82,6 @@ Two remarks on the statement.
one graph among all possible mates; a companion paper treats that
different question.
-1.3 Why degree three is surprising.
-
-Luks proved that isomorphism of graphs of any fixed maximum degree is
-decidable in polynomial time. So on bounded-degree graphs, the strongest
-possible equivalence test, namely isomorphism, is easy. Theorem A says
-that a weaker test, refinement at a prescribed dimension, is EXPTIME-hard
-on the same class. The difficulty is not telling the graphs apart; it is
-deciding what refinement at that particular dimension reports about a
-pair that may well be non-isomorphic.
-
-1.4 Where the ideas come from.
-
-Weisfeiler and Leman introduced the refinement method for graph
-canonization. Cai, Furer and Immerman built non-isomorphic degree-three
-graphs that stay indistinguishable under linearly many counting
-variables; those are lower bounds on dimension, not on the cost of
-deciding refinement. Kiefer and Neuen recorded the joint-update
-convention and the exact (k+1)-pair bijective game used in Section 2.
-For dimension supplied as input, Seppelt proved coNP-hardness of pair
-equivalence and asked about EXPTIME; Lichter, Rassmann and Schweitzer
-independently proved coNP-hardness for simple uncolored graphs. Grohe,
-Lichter, Neuen and Schweitzer compress CFI constructions into smaller
-graphs while keeping long refinement sequences. The product-address,
-scalar-image and corner-potential methods used here are shared with a
-companion paper on unconditional time lower bounds at fixed dimension;
-here the number of binary coordinates grows with the input, so every
-constant is tracked as a function of that number.
-
-1.5 Proof strategy in one page.
-
-We must show two things: membership (a decision procedure inside
-EXPTIME) and hardness (a reduction from an arbitrary EXPTIME language).
-
-Membership is Section 2. Cap the dimension at the number of vertices
-(if k is at least the order, equivalence is just isomorphism, provable
-from the first round alone). Then there are only 2 n^k tuple entries, and
-at most that many rounds before the coloring stabilizes, so the whole
-table computation is 2^(O(n log n)) times a polynomial in the input
-length. That is EXPTIME.
-
-Hardness is Sections 3 through 8.
-
-Fix an arbitrary EXPTIME language L_0 and an input word w of length m.
-Take a deterministic machine M that decides the complement of L_0 and
-halts within T = 2^(p(m)) steps, for a fixed polynomial p with
-p(m) >= m + 2. Put d = p(m) + 2, H = 2^d = 4T, r = 2d, K = r + 1.
-The reduction outputs the two graphs and the dimension k = r.
-
-The intended polarity is
-
- w in L_0
- <=> M rejects w
- <=> the circuit of Link 1 has no true accepting test
- <=> the scalar-image system of Link 2 is consistent
- <=> the graphs of Link 4 or 5 are r-equivalent.
-
-Each "<=>" is a proved equivalence.
-
- Link 1 turns the whole exponential computation into a circuit described
- by polynomially many rules. Times and tape positions are written in
- binary using r bits total; there is one gate of each type at each
- binary address. A "connection schema" gives, for each coordinate, a
- small allowed set of bits and an injective remapping, so one rule
- describes many wires at once. Successor and predecessor are described
- by carry and borrow cases, polynomially many, without listing the
- 2^r addresses.
-
- Link 2 replaces the circuit by constraints on nonempty sets of one- or
- two-bit vectors, one set per variable. Each constraint equates the
- image of one scalar linear form at one endpoint with the image of
- another form at the other endpoint. A true gate output forces the image
- {0}; a false output can keep the full image {0,1}. So the constraints
- are solvable exactly when no accepting test is true. The crucial
- feature is that the equalities are per-comparison, not one global
- assignment: different comparisons may use different vectors from the
- same set.
-
- Link 3 compresses the exponentially many addressed comparisons into
- polynomially many constant-size blocks. Each comparison schema is
- drawn as a long wire; the r binary coordinates of an address are put on
- a cycle; a site is one step of the cycle; a square relates two site
- values across one wire link plus two shared scalar values. Offsets are
- translations taking homogeneous block solutions to affine ones. Offsets
- on different blocks must agree on shared values. The exact projection
- proposition says: on any set of at most K blocks there is a nonempty
- family of compatible offsets, and restricting a family to a subset
- gives exactly the family for that subset. So any choice extends when
- one more block is added. The proof uses shifts at wire types and
- potentials at corners; a closed walk around the whole cycle pins down a
- full address, while on any component that does not wrap the potentials
- can absorb a change of shifts.
-
- Link 4 builds graphs whose vertices are the legal block valuations,
- tagged by private leaves. Duplicator announces a bijection: on each
- currently active block it uses the chosen offset, on every inactive
- block it uses a fresh extension. Spoiler's single chosen vertex then
- activates at most one new block, so the pre-chosen extensions never
- need to agree with each other. Conversely, special zero-valued queries
- are answered by legal valuations, and summing the answers around the
- coordinate cycle produces the scalar images. A ring of marked sites can
- be moved across a wire using one spare pair, which yields exactly the
- required image equalities.
-
- Link 5 does the same with connected graphs of maximum degree three.
- Blocks become paths of valuations connected to prefix trees, with
- equality matchings encoding shared values; a triangle-and-path gadget
- removes the vertex colors. All extra difficulty is in recognition: the
- game must be able to read the encoded data even at a history with every
- pair slot occupied. This is handled by the "reached-history principle"
- from Section 2: a property can be tested in a hypothetical continuation
- that first discards unrelated pairs, and the conclusion then holds
- already at the original history.
-
- Link 6 counts. Every object is polynomial in r + m, and r is polynomial
- in m, so the whole reduction runs in polynomial time and outputs
- polynomial-size graphs with the dimension k = r written in binary.
-
-For readability we use F for the field GF(2) with elements 0 and 1, and
-we write addition in F as +, so 1 + 1 = 0. All vector spaces below are
-over F.
-
-
2. REFINEMENT, THE COUNTING GAME, AND THE UPPER BOUND.
This section has two jobs. It pins down the exact refinement rule and