APSP in $O(n^{2.995561})$ word-RAM steps

Read-back of TrulySubcubicAPSP.apsp_bound_2995561. The theorem has no hypotheses or arguments. It asserts that the problem "APSP" (defined below) is solved in time $O(n^{r})$ on a particular word-RAM model, for the rational exponent

$$r = 2.995561 = \tfrac{2995561}{1000000}$$

(this fraction is already in lowest terms, so its numerator is $2995561$ and its denominator is $10^6$).

What "solved in time $r$" means. For every natural number $\kappa$ there exist a program $P$ (a finite list of machine instructions), a natural number $b$, and a function $T:\mathbb{N}\to\mathbb{N}$ such that:

1. Time bound: there is a natural number $K$ with

$$T(n)^{10^6} \le K \cdot n^{2995561} \quad\text{for all } n \ge 2,$$

i.e. $T(n) \le K^{10^{-6}} n^{2.995561}$ for $n\ge 2$. Nothing is required of $T(0)$ or $T(1)$. 2. Correctness: for every $n \in \mathbb{N}$ (including $n = 0$ and $n = 1$) and every APSP instance $x$ of size $n$ such that every integer $a$ in the input list of $x$ satisfies $|a| \le n^{\kappa}$ (with $0^0 = 1$), and for every word length $W$ with

$$W \ge b\cdot(\lfloor \log_2 n\rfloor + 1)$$

(where $\lfloor\log_2 0\rfloor$ is taken to be $0$; there is no upper limit on $W$), the run of $P$ on $x$ with word length $W$ and step budget $T(n)$ succeeds in the sense below.

The program $P$, the constant $b$ and the function $T$ may depend on $\kappa$, but not on $n$, $x$ or $W$.

The machine. Memory is a map from all integers (including negative ones) to $W$-bit words. Arithmetic is modulo $2^W$; when a word is used as an address, as a branch test, or read as output, it is interpreted as a signed two's-complement integer in $[-2^{W-1}, 2^{W-1})$. Instruction operands $i,j,k$ are fixed integer addresses written in the program, and $[i]$ denotes the word in cell $i$. The instructions are:

• $[i] := 1$ (the word whose unsigned value is $1 \bmod 2^W$; this is the only constant);
• $[i] := [j] + [k]$, $[i] := [j] - [k]$, $[i] := [j]\cdot[k]$, all modulo $2^W$;
• load $[i] := [[j]]$ and store $[[i]] := [j]$ (indirect addressing via the signed value of a word);
• conditional jump: if $[i] < 0$ (signed) go to program position $\ell$, else continue to the next instruction;
• accept; reject (both halt).

There is no division, shift, comparison other than sign test, or bitwise operation. Execution starts at position $0$; executing at a position beyond the end of the program counts as reject. Every executed instruction, including the halting one, costs one step. A run "halts within $t$ steps" if it executes accept or reject at or before its $t$-th step; otherwise it is a failure.

Initial memory. Cell $0$ holds $n$; cells $1, 2, \dots, L$ hold the input list of $x$ (length $L$), each entry reduced to a $W$-bit word (modulo $2^W$); all other cells (all negative addresses and all addresses $> L$) hold $0$.

Success of a run. The run halts within $T(n)$ steps, its verdict is accept (the APSP problem specifies no yes/no condition, so the required verdict is always "accept"), and the final memory, with output value $\mathrm{out}(a)$ defined as the signed integer in cell $1 + L + a$ for $a \in \mathbb{N}$, satisfies the APSP output condition below.

The APSP problem. An instance of size $n$ is a function $w$ assigning to every ordered pair $(i,j)$ of vertices $i,j\in\{0,\dots,n-1\}$ (self-pairs $i=j$ included) either "no edge" or an integer edge weight $w(i,j)\in\mathbb{Z}$ (weights may be negative or zero), subject to the condition that every closed walk has nonnegative total weight: for every vertex $i$ and every walk from $i$ back to $i$ of total weight $d$, $0 \le d$. Here a walk from $i$ to $k$ is a finite sequence of edges $i = v_0 \to v_1 \to \dots \to v_m = k$ (with $m \ge 0$, vertices and edges may repeat), each $v_{s}\to v_{s+1}$ being an edge present in $w$, and its weight is the sum of the edge weights; the empty walk from $i$ to $i$ has weight $0$.

• Input list (length $L = 2n^2$): first the $n\times n$ $0/1$ adjacency matrix in row-major order (entry $(i,j)$ is $1$ if the edge $(i,j)$ exists, else $0$), then the $n\times n$ weight matrix in row-major order (entry $(i,j)$ is $w(i,j)$ if the edge exists, else $0$). The bound $|a|\le n^\kappa$ thus applies to the $0/1$ entries and to all edge weights.
• Output condition: for every pair $(i,j)$, with $p = i\cdot n + j$, $\mathrm{flag} = \mathrm{out}(2p)$ and $\mathrm{dist} = \mathrm{out}(2p+1)$, exactly one of the following holds (they are mutually exclusive):
  • $\mathrm{flag} = 1$, there is a walk from $i$ to $j$ of weight exactly $\mathrm{dist}$, and $\mathrm{dist} \le e$ for the weight $e$ of every walk from $i$ to $j$ (so $\mathrm{dist}$ is the minimum walk weight); or
  • $\mathrm{flag} = 0$ and there is no walk at all from $i$ to $j$ (in this case $\mathrm{dist}$ is unconstrained).

In particular, for $i = j$ the empty walk exists, so the flag must be $1$ and, by the nonnegative-closed-walk condition, $\mathrm{dist}$ must be $0$.

Edge cases. For $n = 0$ the input list is empty, the size bound is vacuous, the word-length condition is $W \ge b$, and the output condition is vacuous, so the program need only accept within $T(0)$ steps. For $n = 1$ the size bound forces all input entries into $\{-1,0,1\}$. For $\kappa = 0$, all edge weights must lie in $\{-1,0,1\}$ for every $n$. If $b = 0$ is chosen, the requirement includes word length $W = 0$ (every word is $0$). Correctness is demanded simultaneously for all sufficiently large $W$, however large. The integer $n$ placed in cell $0$, the input entries, and the outputs are all subject to reduction modulo $2^W$ and signed reading.