Proof. Let \(\Gamma\) be the fixed tape alphabet and let \(\Sigma\) consist of its plain symbols together with symbols carrying a head state of \(M\). There is a fixed map \[F:\Sigma^3\longrightarrow\Sigma\] that updates the center cell of every configuration with exactly one head. If the head is at the center, its state and scanned symbol determine the symbol written there and whether the head remains. If it is at a neighbor, that neighbor’s marked symbol determines whether the head moves into the center and, if so, its new state; the center’s tape symbol is already in the triple. If the triple has no head, the center stays unchanged. These rules also cover halted states, for which nothing changes. Complete \(F\) arbitrarily on triples impossible in a one-head configuration.

The same rule implements one machine step on a ring of length \(H_*\). Starting from one head, it writes at that head and transfers the head by the prescribed displacement, so the ring still has exactly one head. In particular, a triple crossing the ring’s seam is a prescribed valid local case, not an arbitrary entry of the table.

Initialize the ring with \(w\) at \(0,\ldots,m-1\), the head at zero, and blanks elsewhere; for \(m=0\) the head carries a blank. This simulates the line computation through halting. All input positions and all positions visited within \(T\) steps lie in \([-T,T]\), since \(m\le T\). Reduction modulo \(4T\) is injective on this interval, and the initial contents at these positions agree with the corresponding ring cells. Inductively, each scanned ring cell has received exactly the same previous writes as its unique potentially visited line counterpart. The next transition therefore writes the same symbol and moves to the same corresponding position, including a last move to either endpoint of the interval. There can be no change elsewhere: a valid machine update changes only the old and new head cells. Equivalently, all neighborhoods that could react to the head lie in the halo \([-T-2,T+2]\), whose \(2T+5\) positions are distinct modulo \(4T\) because \(T\ge4\); centers with no head in their triple stay unchanged. Upon halting the whole ring configuration freezes. Its configuration at time \(H_*-1\) consequently records the outcome of \(M\).

Proof. We first describe the constraints for the expanded finite circuit, then give their product representation. A scalar gate has one scalar variable; its input and output directions are both the identity. An AND gate has a vector variable \((x_1,x_2)\in\mathbb F_2^2\). Its two input directions are the coordinate projections, and its output direction is \(x_1+x_2\).

Introduce one dummy scalar variable. For each seed, compare its scalar direction with the constant-zero form on the dummy. For each test, compare its scalar direction with the constant-one form on the dummy. The dummy may have any nonempty set of values: its two constant forms have images \(\{0\}\) and \(\{1\}\), respectively, without any restriction on that set.

For each individual connection, with source output direction \(o\) and destination input direction \(s\), introduce a private buffer \((z,z')\in\mathbb F_2^2\) and impose the three separate image comparisons denoted by \[ o=z,\qquad o=z',\qquad z+z'=s. \tag{13}\] The first two equalities do not require a common source value to be simultaneously equal to both buffer coordinates.

Proof. Choose an exponential-time decider for the complement of \(L_0\), by swapping the two halting outputs of a decider for \(L_0\). A fixed multitape machine can be simulated on one tape with polynomial overhead: store its tapes and head markers on fixed tracks, and scan the used interval to collect scanned symbols and then perform the updates. After \(t\) simulated steps the interval has length \(O_M(m+t+1)\); a fixed number of scans per step gives polynomial total overhead. Enlarging a fixed integer polynomial \(p\) absorbs that overhead and ensures \(p(m)\ge m+2\). Apply 7 to this normalized complement decider, then 9. Consistency is equivalent to all tests being false, hence to \(M\) not accepting \(w\), which is equivalent to \(w\in L_0\). The exact buffer counts give the claimed description size. Since \(r\) is polynomial in \(m\) for fixed \(p\), the generation time is polynomial in \(m\) as well. ◻

Proof. A site has \(2^{d_t}\le4\) valuations in either version. A square at a link \(tu\) has \(2^{d_t+d_u+1}\le16\), since at least one link endpoint is internal. The site assertion is immediate. In a square, the two verticals are distinct, each with coefficient one in [eq:square-equation]. The equation is therefore a nonzero scalar linear equation with a possibly nonzero right-hand side. Its homogeneous kernel is \(\mathcal Z_B^0\), and each nonempty fiber is a coset of that kernel. After prescribing any one readout, at least one vertical remains free and can be set to satisfy the equation. This proves both nonemptiness and the projection assertion, including when the prescribed readout is a two-bit horizontal. Finally, the two horizontals contribute at most four bits in total and the two verticals contribute two more. ◻

Proof. The support is connected because the corner component is connected. Only square blocks introduce support links, so it has at most \(\abs{U}\le K\) distinct links. Internal wire types are private and have degree two in the full wire layout. A path connecting distinct real types, or a cycle in that layout, must therefore contain a whole wire, which has \(4K+1>K\) links. Neither can occur in this support. This also excludes a cycle created by a loop schema or by parallel schemas. The stated descriptions follow by following the private wire interiors from the unique real type, if one is present. ◻

Proof. Take a marker-one closed walk. Let \(c_i\in\mathbb F_2\) be the parity of its horizontal traversals in row \(i\). Counting incidences at all corners on boundary \(i\) gives \[c_{i-1}+c_i=0.\] Indeed, the total incidence count of a closed walk at those corners is even, and a vertical traversal contributes twice on the same boundary. Since the marker sum is \(c_r=1\), all \(c_i\) equal one. Each row therefore contributes a horizontal edge to the walk, and every block has horizontals in just one row. This proves the first assertion.

With exactly \(r\) blocks, there must be one block in every row. The witness walk meets all of them, so all lie in its corner component. Use the alignment of that component, or of any containing corner component in \(\Gamma_U\). The horizontals of the unique row-\(i\) block prescribe one aligned label at boundary \(i\) and one at boundary \(i+1\): for a square the two horizontals have the same aligned labels because of its vertical matches.

Now count incidences at boundary \(i\) separately for each aligned label. Vertical traversals contribute an even number of incidences to that label. The total horizontal contribution from each neighboring row is odd and occurs at that row’s prescribed label. The labels prescribed by rows \(i-1\) and \(i\) must therefore agree. Their common value is the \(i\)-th coordinate of the recovered address. This proves existence and uniqueness.

Two \(r\)-element subcollections of a set of size at most \(r+1\) share at least \(r-1\) blocks. In the present setting these common blocks have distinct rows. In particular, the two subcollections are in the same corner component. Every boundary is incident with a common row, since at most one row is missing from the overlap and \(r\ge3\). Its address coordinate is consequently the same for both subcollections.

Finally, a support without a real type is inside one wire by 13. All its internal matches are identities. Every recovered coordinate is the label of a corner at an internal type, and hence lies in \(A_{e,i}\). Reading all coordinates gives an address in \(A_e\). ◻

Proof. If the support has no real type, all its types lie in one wire interior. Its equations merely identify their scalar shifts. Choose any scalar, or any element of \(D_{e,\mathbf a}\) when that condition is present. If the support has a real type \(P\), choose any vector in \(\mathbb F_2^{d_P}\), or any vector of \(Q_{P,\mathbf a_P}\) when required. The endpoint equation then determines the scalar along each incident arm, and the interior equations propagate it along that arm. The arms do not meet, so there is no further compatibility requirement. ◻

Proof. We have \(\abs{V}\le r\). By 14, \(C_0\) uses exactly \(r\) blocks. Its recovered address is the one used for \(C\), expressed in the respective coordinate systems. There are three cases.

If the support of \(C_0\) contains a real type \(P\), it is also the unique real type of \(C\). The admissible systems on either component are parameterized by the same vector \(h_P\in Q_{P,\mathbf a_P}\); that vector determines the scalars on all of their arms. Restriction preserves this parameter and is onto.

If the support of \(C\) has no real type, both components are inside the same wire \(e\). Their admissible systems are parameterized by the same scalar in \(D_{e,\mathbf a}\), so restriction is again onto.

In the remaining case, \(C\) contains a real type \(P\), but \(C_0\) does not. The connected support of \(C_0\) lies inside one arm at \(P\), belonging to a wire \(e\). Its recovered internal address \(\mathbf a\) belongs to \(A_e\). Therefore the ambient permutation transport from that address to the incident real endpoint agrees, on every coordinate, with the actual endpoint map: it is the identity if \(P\) is the first endpoint, and \(\boldsymbol\sigma_e\) if \(P\) is the second. Thus the map from the parameter for \(C\) to the parameter for \(C_0\) is respectively \[\phi_{e,0}:Q_{P,\mathbf a}\longrightarrow D_{e,\mathbf a}, \qquad\text{or}\qquad \phi_{e,1}:Q_{P,\boldsymbol\sigma_e(\mathbf a)} \longrightarrow D_{e,\mathbf a}.\] The applicable map is onto by [offset:eq-wire-images]. Once its preimage has been chosen, all the other arm scalars of \(C\) are determined and admissible. Only the incident endpoint of this arm is used, so the argument also covers a loop wire. Injectivity of the endpoint form is not required. ◻

Proof. Put \(g_t=\widetilde h_t+h_t\). Adding the two copies of the link equation gives \[ L_{\ell,t}g_t=L_{\ell,u}g_u \quad\text{on every support link }\ell=tu. \tag{21}\] Since \(C_0\) is nonwrapping, the marker sum is zero on every closed walk. Choose one corner as a root, and define \(s_v\in\mathbb F_2\) to be the marker sum along a path from it to \(v\). This is independent of the path: the concatenation of two such paths, reversing one, is a closed walk. Consequently \[s_v+s_w=\omega(vw)\] on every named edge.

Replace the old potential at a corner of type \(t\) by \(\widetilde M_v=M_v+s_vg_t\). On a horizontal in row \(i\), the change in [offset:eq-potentials] is \[(s_v+s_w)g_t+\delta_i(\widetilde h_t+h_t) =(\delta_i+\delta_i)g_t=0.\] On a vertical, \(s_v=s_w\), so the change is \[s_vL_{\ell,t}g_t+s_wL_{\ell,u}g_u=0\] by [offset:eq-shift-difference]. Thus all old readout values are preserved. The argument allows vector shifts at a two-dimensional real type and does not require its endpoint forms to be nonzero. ◻

Proof of 12. Use the families defined by [offset:eq-potentials]. Nonemptiness, legality, and agreement on shared readouts have already been proved. It remains to establish the projection equality. The case \(V=U\) is immediate, so suppose \(V\subsetneq U\). Then \(\abs{V}\le r\). Each component \(C_0\) of \(\Gamma_V\) lies in a component \(C\) of \(\Gamma_U\).

First take a represented list in \(\mathcal H_U\) and restrict its shifts and potentials to each \(C_0\). These shifts satisfy all old link equations. If \(C_0\) is nonwrapping, it has no additional address condition. If it wraps, their admissibility follows from 16. The restricted representation therefore belongs to \(\mathcal H_V\), proving \(\mathcal H_U|_V\subseteq\mathcal H_V\).

For the other inclusion, fix an arbitrary list in \(\mathcal H_V\), and choose any one of its representations by admissible old shifts and potentials. There is at most one wrapping old component: one would already require \(r\) of the at most \(r\) old blocks. For each component \(C\) of \(\Gamma_U\), choose an admissible new shift system. If \(C\) contains the wrapping old component \(C_0\), choose it to extend the selected old shifts on \(C_0\), using 16. On all other new components choose any admissible shifts.

Keep the old potentials on a wrapping old component. On every nonwrapping old component, apply 17 to replace its old shifts by the restriction of the chosen new shifts without changing any old offset. Distinct old components have disjoint corner sets, so these potential changes coexist even when several old components merge into a single new component or have different old shifts at the same type. Assign arbitrary potentials to the additional corners of \(\Gamma_U\).

The new shifts and these potentials represent a member of \(\mathcal H_U\). They satisfy every new square equation by [offset:eq-potentials], while on each old named edge the value is unchanged. Hence this member restricts to the prescribed list in \(\mathcal H_V\), proving the reverse inclusion. ◻

Proof. The adjacency rule and owner rule introduce no loops or multiple edges. Each block has nonempty legal fibers of equal cardinality, so the two graphs have equal positive orders. Each block has at most \(64\) valuations, a convenient loose constant, hence \(J\le N\le64J\). The total order is at most \[N+NJ(N+1)=O(J^3).\]

Translation by a legal affine offset bijects \(\mathcal Z_B^0\) with \(\mathcal Z_B^1\). All owners in block \(B\) have the same number of leaves, so the displayed map is a bijection of the entire part. Within a base block it preserves equality, and there are no base edges. Between distinct active blocks the offsets agree on every shared readout; adding equal offsets preserves both agreement and disagreement on each name, hence the entire condition (22). Blocks with no common name stay nonadjacent.

A leaf is adjacent only to its owner. For a base vertex in the owner’s block the same translation is applied to the base and the owner, whether or not the owner itself is marked, so their equality is preserved. A base in a different block remains a nonowner. Distinct leaves stay distinct because owner translation is injective and the local index is unchanged. Repeated selections, different leaves at one owner, and leaves at different owners are therefore all handled. Leaf–leaf adjacency is absent, and no leaf is identified with a base vertex. This proves the induced-subgraph claim on any union of compatible parts.

For recognition, first observe that a marked pair reached under any winning strategy with at least two slots has equal degrees. After discarding every other pair, request another slot. The announced bijection must preserve adjacency to the retained pair for every choice, and therefore matches its two neighborhoods bijectively. This is a property of the reached history, not a test that needs spare slots in that history.

Every leaf has degree one. A base vertex in block number \(j\) has degree in \[[j(N+1),\,j(N+1)+N-1].\] These intervals are disjoint and have lower endpoints greater than one. Thus every reached base response is a legal valuation in the same block. Distinct homogeneous zero vertices sharing a readout are adjacent, so their responses must satisfy (22) and agree on all shared names. ◻

Proof. A spine vertex has at most two spine neighbors and one leaf neighbor. A nonroot internal tree vertex has one parent and at most two children. A nonleaf root has at most two children and one further neighbor: its anchor in channel zero, or its matched opposite root in a proper channel. A leaf has its spine neighbor and either its parent or, when it is also a root, its matched opposite root. An anchor has its channel-zero root neighbor and at most two neighbors on the anchor path. Thus every degree is at most three.

All tree, spine, and anchor vertices occupy distinct positions. A proper root belongs to just one channel and has just one matching edge. Its opposite root belongs to a different block. The remaining edge types have their distinct indicated endpoints, so no loop or multiple edge is introduced.

Every legal prefix has a full legal extension. It therefore reaches a leaf, then the spine at that channel. The spine path reaches channel zero at the same valuation, and the channel-zero tree reaches the anchor. This proves connectedness of each block part. The anchor path joins all parts.

There are at most \[N+\sum_{B\ne C}\abs{\mathcal R(B)\cap\mathcal R(C)} \le N+4N(N-1)\] channels in total. A channel has at most \(2^6\) spine vertices and at most \(\sum_{h=0}^6 2^h\) tree vertices. It also has at most eight sorts: one spine sort and at most seven tree-level sorts. Adding the \(N\) anchors and anchor sorts proves both estimates. ◻

Proof. Starting at channel zero of \(B\), follow its spine to \(c_B(C,\rho)\), then go to the leaf and ascend its tree to the root. Cross the matching to the opposite root in \(C\). Descend to a leaf, go to its spine, and follow the spine to channel zero of \(C\). Record the sort at every position of this route. When a root is also a leaf it contributes just one position. The route is illustrated in 4.

The sorts specify the block and channel throughout, and the level of each tree vertex. Every spine step preserves the full valuation. The leaf is indexed by that valuation, and truncation to the root retains exactly the coordinates of \(\rho\). The prescribed step to the opposite root can only use the matching of equal values. A descent on the other side extends that same root value, and its subsequent spine steps preserve the chosen extension. Consequently every walk with the specified sorts has equal endpoint readouts. Conversely, when the endpoint readouts agree, their two prefix paths reach a matched pair of roots and give the required walk. ◻

Proof. Translation by \(\xi_B\) bijects \(\mathcal Z_B^0\) with \(\mathcal Z_B^1\). Its effect on a prefix depends only on that prefix and commutes with truncation. The displayed maps therefore give bijections at every sort, preserving the tree, leaf-to-spine, and consecutive-channel edges and their nonedges. The empty prefix is fixed, so the anchor edge is preserved.

The only edges between parts are anchor-path edges and root-matching edges. Anchors are fixed individually. For a root matching on \(\rho\), roots with values \(u,v\) are adjacent exactly when \(u=v\). If both block offsets have the same restriction \(d\) to \(\rho\), then \[u=v\quad\Longleftrightarrow\quad u+d=v+d.\] This preserves both adjacency and nonadjacency across that matching. Different channels stay different channels, so no other cross-part adjacency can arise. ◻

Proof. Every triangle member has degree three. A connector has its triangle neighbor and its first path neighbor, and, precisely when its port is used, one external connector neighbor. Its degree is therefore two or three. All other path vertices have degree at most two. The edge lists introduce neither loops nor repeated edges. Each replacement is connected, and replacements are joined exactly along the original graph’s edges; hence \(X^\varepsilon\) is connected. There is at least one block, each with nonempty legal valuations, so the order is positive.

Fix a block and offset, and write \(v'\) for the image of a vertex \(v\) under its colored block translation. Define a permutation of the three ports at \(v\) to those at \(v'\) as follows.

1. A port used by an edge within the block goes to the port used by the image of that edge under the colored translation.

2. At an anchor, a port used by an external anchor-path edge goes to the port for the anchor-path edge toward the same other block.

3. At a proper-channel root, the port used by its edge to the opposite root goes to the port for the unique such edge at its image root.

4. The unused ports are matched in their fixed numerical orders.

These prescriptions are disjoint and exhaustive. Internal incidences are bijected by a within-block isomorphism. Each anchor retains the same external anchor incidences, and each proper root has exactly one external incidence at both source and image. Thus the unused port counts also agree, and the prescriptions indeed give a permutation. Crucially, the third prescription does not require the neighboring block’s offset.

Using this port permutation, map triangle members to triangle members, connectors to connectors, and private paths in order to their corresponding private paths. The colors of \(v,v'\) agree, so the path lengths agree. This gives a bijection \(\Psi_{B,\xi_B}\) of the block parts, with the asserted action on the distinguished triangles.

For compatible offsets on a union of blocks, every internal edge and every anchor edge is carried to the edge prescribed by its endpoint port permutations. For an equality matching, the root values are shifted by the same readout offset, so the equality condition is preserved in both directions. At its two endpoints the unique external ports are exactly the ports used by that matching. Unused ports remain unused, and all channels remain their own channels. It follows that all edges and nonedges between replacements in the union are preserved. The maps inside the replacements are also isomorphisms, proving the induced-subgraph assertion. Edges leaving the union impose no condition on unchosen offsets.

For equal orders, choose an arbitrary legal offset separately at each block. The resulting bijections of disjoint parts give a bijection of the two vertex sets; compatibility is not needed for this count. Finally, if the number of sorts is \(s\), a colored vertex of color \(c\) produces exactly \(6+3c\) vertices. By 22, both \(s\) and \(\abs{V(Y^\varepsilon)}\) are \(O(N^2)\), giving the order bound \(O(N^4)\). All enumerations use at most six-bit valuations and prefixes, explicit block pairs and shared names, and paths of polynomial length. They therefore implement the construction in polynomial time. ◻

Proof. Degrees and triangles. Retain a paired vertex and request one further slot. For every vertex Spoiler could choose, Duplicator’s announced bijection must preserve adjacency to the retained vertex. The bijection therefore takes its neighbor set onto the other neighbor set, proving degree equality with two slots. To test membership in a triangle, retain the vertex and mark the two other triangle members, using three slots. The converse can be tested in the second graph: after a bijection is announced, Spoiler can choose the preimage of any desired second-graph vertex. Partial isomorphism then proves triangle membership in both directions.

The only triangles in \(X^\varepsilon\) are the designated replacement triangles. Indeed, private path vertices cannot lie in a triangle; a connector has only one triangle-vertex neighbor; and edges between connectors form a matching, since each connector is a single port. There are no other edges between replacements. Thus a response to a triangle member lies in a unique replacement triangle.

Sort recovery. Retain such a pair, and mark the connector attached to its first-graph triangle member. By triangle membership and adjacency, its response is the unique nontriangle neighbor of the second-graph triangle member. At a connector, the first private-path vertex is its unique neighbor of degree below three. The triangle member has degree three, and any connector reached across an external connector edge has degree three because that port is used. This assertion also covers an unused connector and a private path of length one. Consequently a third mark forces the first private-path step.

Continue along the source path, retaining the previous and current vertices and using a third slot for the next vertex. Adjacency and inequality from the previous vertex force the forward step in the target private path. The original triangle mark can be discarded once the traversal has started. If the lengths differed, at their first discrepancy a terminal vertex of degree one would be paired with an internal vertex of degree two. The degree invariant excludes this. The path lengths, and therefore the sort numbers, are equal. All assertions used during this test are invariants of reached winning histories, established by their own alternative continuations.

Underlying adjacency. Retain the two marked triangle representatives over \(v,w\), and also mark the actual triangle ports used by \(vw\) and the two connectors attached to those ports. This requires at most six slots. An actual port may already be the representative; duplicate marking is allowed, or its extra mark may be omitted. Its response lies in the same triangle as its original representative, by equality in the coincident case and by adjacency and triangle membership otherwise. Each connector response must be the unique nontriangle neighbor of its port response. The two connectors are adjacent, so their underlying auxiliary vertices are adjacent in \(Y^1\). The two response representatives cannot belong to one triangle: the source representatives are distinct and nonadjacent, whereas distinct members of one triangle are adjacent.

Distinguished vertices and shared readouts. Sort recovery sends a triangle over a channel-zero spine vertex of block \(B\) to a triangle over another channel-zero spine vertex of that same block. The legal valuation indexing this vertex gives the unique decoded response.

Suppose now that the two source valuations at distinct blocks agree on a shared readout. Their distinguished vertices admit the sort-prescribed walk from 23. First discard all marked pairs except these two endpoint pairs. Mark triangle members over the intermediate vertices successively, always retaining both endpoints and at most two consecutive intermediate pairs. Four slots suffice. Sort recovery gives the required sorts of all response vertices. Underlying adjacency, applied to each consecutive pair when both are marked, shows that the responses trace a walk of precisely the prescribed sorts. 23 now forces equality of the response readouts.

The four walk slots need not be supplemented by six adjacency-test slots. Underlying adjacency is already an invariant of every reached winning history: its proof may discard the unrelated endpoint pairs in a different continuation. Similarly, the unary tests need not retain the other walk marks. The largest simultaneous test uses six slots, and the conclusion about the retained endpoints therefore holds already at the original history, regardless of its occupancy. ◻

Proof of 21. The graph promises, equal orders, size bound, local lifts, and compatible-union isomorphisms are [graph:colored-promises,graph:uncolored-lifts]. The distinguished triangles have the stated indexing by construction. Since \(K=r+1\ge9\), 26 supplies the decoding and shared-readout invariants. ◻

Proof. Use \(\mathcal D_B^\varepsilon(z)=T_B^\varepsilon(z)\) in 19. The block maps and decoding properties are exactly those proved in 21; its parameter condition holds because \(r\ge8\). ◻

Proof. Since \(p(m)\ge m+2\), we have \(m\le r\). The number of original consistency types and schemas is therefore \(O_M((r+1)^2)\), and every vector dimension is at most two. Each schema has \(r\) constant-size binary coordinate entries. Subdividing each wire with \(4(r+1)\) internal types gives \(O_M((r+1)^3)\) types and links. Even copying an entire \(r\)-coordinate table onto every link requires only \(O_M((r+1)^4)\) entries.

For each type or link and each row there are at most four blocks: one chooses two binary labels, or two label matches each determined by a binary label. A site has at most four legal valuations. A square has two vector readouts of dimensions at most two and two scalar readouts, hence at most \(2^6\) valuations, a deliberately loose bound. Thus both the number \(J\) of blocks and the common number \(N\) of base vertices are \(O_M((r+1)^4)\); moreover \(J\le N\) because every block has a legal valuation in each version. There are at most \(J(N+1)\) leaves at any base vertex, giving total order \[ N+NJ(N+1)\le N+N^2(N+1)=O_M((r+1)^{12}). \tag{28}\] The two output matrices have \(O_M((r+1)^{24})\) entries in total. There is at least one scalar real type, which alone supplies four sites per row and two valuations per site. The graph order is at least \(8r\), so the output parameter is below the order.

Here is an explicit polynomial-time implementation. All lists are stored sequentially, so no unit-cost random access is assumed.

1. Count \(m\), evaluate the fixed polynomial \(p\), and set \(d,r,K\). Enumerate the fixed machine alphabet, carry and borrow cases, initial positions, and final-time tests. Fill each product table coordinate by coordinate. Only the \(\max\{1,m\}\) exceptional initial positions and the \(d+1\) possible blank suffix domains are generated. Apply the buffer and dummy construction and enumerate wire and link identifiers.

2. Enumerate the constant number of local label choices for each type-row or link-row pair. Record the named readouts of each block and enumerate all of its local valuations. Test its affine or homogeneous equation directly. Count \(N\) and enumerate leaves by an owner identifier and a local index. This produces vertex lists in both graph versions.

3. Enumerate ordered pairs of vertices and stream the corresponding matrix bits. For base vertices, compare the constant number of named readouts and their values, and check that the blocks differ. For a pair involving a leaf, test owner incidence. Leaf–leaf pairs are nonadjacent. The diagonal is zero. Finally write \(r\) in binary.

For a concrete bit-cost allowance, these descriptions use \(O_{M,p}((r+2)^{12})\) records, each of at most \(O_{M,p}((r+2)^2)\) bits; this includes full coordinate tables, identifiers, valuation lists and counters. Allow the larger total work-space length \[D=O_{M,p}((r+2)^{16}).\] The stated loops need at most \(O_{M,p}((r+2)^{24})\) record-generation trials and matrix entries. Each uses at most \(O_{M,p}((r+2)^2)\) elementary lookups, copies, comparisons or arithmetic operations; constructing a coordinate table can scan all \(r\) entries. A sequential list lookup or an elementary binary arithmetic operation on at most \(D\) bits costs \(O(D^2)\) time by ordinary scanning and schoolbook algorithms. The total allowance is thus \(O_{M,p}((r+2)^{24+2+32})\), which is within the asserted exponent 80.

Polynomial evaluation also fits this budget even if \(p\) has signed coefficients and cancellations. If \(p(x)=\sum_{i=0}^q c_i x^i\) and \(A_p=1+\sum_i|c_i|\), every Horner intermediate at \(m\ge0\) has absolute value at most \(A_p(m+1)^q\). Its bit length is \(O_p(\log(r+2))\), and the number \(q\) of arithmetic stages is fixed. The case \(m=0\) has \(p(0)\ge2\) and causes no exception. Reading the input and writing the \(O(\log r)\)-bit dimension are included. At no stage is the list of \(2^r\) full addresses, the \(2^d\) computation times, a consistency witness, or an offset family enumerated. ◻

Proof. We give explicit polynomial bounds and a construction that uses only the compressed descriptions. Since \(p(m)\geq m+2\), we have \(r\geq 8\) and \(m\leq b_*\). The computation construction produces \(O_M((r+1)^2+m)=O_M(b_*^2)\) real types and comparison schemas. Their value dimensions are at most two. A schema is described by its endpoint identifiers, its two constant-size affine forms, and \(r\) constant-size coordinate domains and maps.

Each comparison wire has \(4K\) private internal types and \(4K+1\) links. Thus the subdivided layout has \(O_M(b_*^3)\) types and links. At a fixed row and type there are at most four choices of a site’s pair of labels; at a fixed row and link there are at most four choices of a square’s two coordinate matches. Multiplying by \(r\) rows gives \[ \abs{\mathcal B}=O_M(b_*^4). \tag{29}\] A block has at most four readout names. The total number of proper channels, indexed by ordered pairs of distinct blocks and a shared name, is therefore at most \(4\abs{\mathcal B}^2\). Including channel zero at every block, the total number of channels is \(O_M(b_*^8)\).

Every legal valuation uses at most six bits by 11. Hence a channel has at most \(2^6\) spine vertices, at most seven prefix levels, and at most \(2^6\) vertices on any one of those levels. These are absolute constants, independent of \(r\). There are also only constantly many vertex sorts per channel and one anchor and anchor sort per block. Consequently, \[ \abs{V(Y^\varepsilon)}=O_M(b_*^8),\qquad s=O_M(b_*^8), \tag{30}\] where \(s\) is the number of positive integer sort colors.

A colored vertex of color \(c\) is replaced by three triangle vertices, three connectors, and three private paths with \(c\) new vertices each. The replacement therefore has exactly \(6+3c\) vertices. Since \(1\leq c\leq s\), (30) gives \[ \abs{V(X^\varepsilon)} \leq (6+3s)\abs{V(Y^\varepsilon)}=O_M(b_*^{16}). \tag{31}\] The two explicit output matrices have \(O_M(b_*^{32})\) entries, and the output dimension \(r\) has \(O(\log b_*)\) binary bits.

All structural promises follow from 21. In particular, equal order does not require a compatible global offset: each individual block has a nonempty affine valuation space, and any of its legal offsets supplies a bijection between its two block parts. Their separate cardinalities agree and can be added over the partition. There is at least one site block and a legal valuation in each version, so the common graph order is positive. Degree-one and degree-two vertices are permitted because the required bound is at most three.

For completeness, the construction can be implemented with the following finite lists and loops.

1. Evaluate the fixed polynomial \(p\) and generate the circuit’s schema domains and coordinate maps by the carry, borrow, and initialization cases of 7. Expand each connection into its comparison schemas, subdivide each comparison wire, and enumerate the type, link, and block lists. A coordinate scan has length \(r\); none of these steps ranges over the full set of addresses.

2. Compare the at most four names of each ordered pair of blocks to enumerate channels and their opposite-channel identifiers. For every channel, enumerate bit strings of length at most six to list its legal valuations and occurring prefixes. A prefix occurs if one of the constantly many full strings extending it satisfies the local equation. Enumerate the sorts to assign their positive color numbers. Fix all ordering choices by the same nested enumeration rules in the two versions.

3. Form the auxiliary vertex and edge lists from the defining rules. For example, enumerate unordered pairs of auxiliary vertices and test those rules. Assign a vertex’s incident ports in generated edge order; the list has length at most three. Generate the triangle, connector, and private-path vertices using the sort numbers as path-length counters.

4. Enumerate pairs of output vertices and write their adjacency bits. A vertex record contains its original auxiliary vertex, its triangle/connector/path kind, its port, and, for a path vertex, its distance from the connector. With the old edge and port lists, the replacement rules decide adjacency from such records.

All local valuation tests have constant dimension. The witness sets and the families \(\mathcal H_U\) are used only in the correctness proof and are never constructed by this algorithm.

Here is a deliberately loose bit-time accounting on a deterministic multitape machine. Individual records, coordinate tables, and counters can be padded to \(O_{M,p}(b_*^2)\) bits. Identifiers and counters need only \(O_{M,p}(\log b_*)\) bits, and individual schema tables use \(O(r)\) entries; even a time or position address has only \(d=r/2\) bits. There are at most \(O_{M,p}(b_*^{32})\) records if the output matrix bits are included, so \(O_{M,p}(b_*^{40})\) bits suffice for lists and working storage, including scratch space. The fixed polynomial \(p\) is evaluated on polynomially bounded integers by ordinary integer arithmetic.

The ordered block-pair loop has \(O_M(b_*^8)\) iterations, the auxiliary vertex-pair loop has \(O_M(b_*^{16})\), and the output pair loop has \(O_M(b_*^{32})\). The other enumeration loops have no larger count. The work of each iteration can be expressed using \(O_{M,p}(b_*^2)\) basic record operations: identifier lookup or update, copying, comparison, and elementary integer arithmetic. In particular, edge information can be stored as endpoint and port records, without copying whole adjacency rows into vertex records. The total number of these operations is bounded by \(O_{M,p}(b_*^{40})\).

Implement an identifier lookup by a sequential scan of the stored lists; all basic record operations can conservatively be bounded by the square of the allowed tape length, using sequential scans and schoolbook arithmetic. Thus the preceding bounds give time at most \(O_{M,p}(b_*^{120})\), which is within the stated \(O_{M,p}(b_*^{160})\) allowance. No constant or threshold in this implementation depends on a separately fixed value of the growing dimension. Finally, \(b_*\) is polynomial in \(m\) for the fixed polynomial \(p\), so this is deterministic polynomial time in the source input length. ◻

Proof of 1. Membership for both languages is 4, including invalid encodings and dimensions larger than the graph order.

For hardness, fix any binary language \(L_0\in\mathsf{EXPTIME}\). Choose a normalized deterministic decider \(M\) for its complement and a fixed polynomial \(p\) as in 10. On \(w\) of length \(m\), generate the product circuit and its scalar-image instance at \(r=2(p(m)+2)\ge8\). For \(\textnormal{\textsc{WL-Equiv}}\), use the general realization; for \(\textnormal{\textsc{Subcubic-WL-Equiv}}\), use the connected subcubic realization. Output the two explicit adjacency matrices and \(k=r\) in binary. The compiler bounds are, respectively, \(O_{M,p}((r+2)^{80})\) and \(O_{M,p}((r+2)^{160})\). Since \(p\) is fixed, both are polynomial in \(m\); their polynomial degrees may depend on the source language, as permitted for a many-one reduction.

All required graph promises hold on every input, whether accepted or rejected by \(M\). The two realization propositions verify the hypotheses of 19. Together with the computation reduction, this gives, for either output pair \(W^0,W^1\), \[\begin{aligned} w\in L_0 &\Longleftrightarrow M\text{ does not accept }w\\ &\Longleftrightarrow \text{the circuit has no true terminal test}\\ &\Longleftrightarrow \text{the scalar-image instance is consistent}\\ &\Longleftrightarrow W^0\equiv_r W^1. \end{aligned}\] Thus each construction is a deterministic polynomial-time many-one reduction with the required polarity. Because \(L_0\) was arbitrary, both target languages are \(\mathsf{EXPTIME}\)-hard. No dimension-dependent threshold or fixed-dimension lower bound supplies a step of these uniform reductions. ◻

Proof. For membership, convert the unary dimension to binary and apply 4; the conversion is polynomial in the input length. For hardness, the reductions just proved output \(k=r=2(p(m)+2)\), which is polynomial in the source input length \(m\). Writing this dimension in unary therefore preserves their polynomial running time. The output graphs and the equivalence condition are unchanged. ◻