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

Read-back of TrulySubcubicAPSP.apsp_bound_2996001.

The statement. The problem "APSP" (defined below) is solved in time $r$ with $r = 2.996001$, read as the rational number

$$r = \frac{2996001}{1000000}$$

(already in lowest terms: numerator $2996001$, denominator $10^6$). Unfolding "solved in time $r$", the claim is:

For every natural number $\kappa$ there exist a program $P$ (a finite list of machine instructions, below), 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)^{1000000} \le K\cdot n^{2996001}\qquad\text{for all } n\ge 2$$

(this is the stand-in for $T(n)=O(n^{2.996001})$; nothing is required of $T(0)$ or $T(1)$); 2. (correctness) for every $n\in\mathbb N$, every APSP instance $x$ of size $n$ all of whose input numbers $a$ satisfy $|a|\le n^{\kappa}$, and every word length $W\ge b\cdot(\lfloor\log_2 n\rfloor+1)$ (with $\lfloor\log_2 0\rfloor$ taken as $0$), the program $P$ solves $x$ at word length $W$ within $T(n)$ steps (meaning made precise below).

The order of quantifiers is $\forall\kappa\;\exists P,b,T$: the program, constant $b$ and time function may depend on $\kappa$, but not on $n$, $x$ or $W$. There is no upper limit on $W$: the same $P$ must be correct with the same step budget $T(n)$ at every word length from the threshold upward.

The instance. An APSP instance of size $n$ is a function $w$ assigning to each ordered pair $(i,j)$ of vertices $i,j\in\{0,\dots,n-1\}$ either "no edge" or an edge with integer weight $w(i,j)\in\mathbb Z$ (self-loops $i=j$ allowed, any sign of weight allowed), subject to the hypothesis that every closed walk has non-negative total weight. Here a walk/path from $i$ to $k$ of weight $e$ is defined inductively: the empty walk at $i$ goes from $i$ to $i$ with weight $0$; and if there is an edge $i\to j$ of weight $d$ and a walk from $j$ to $k$ of weight $e'$, then there is a walk from $i$ to $k$ of weight $d+e'$. Walks may repeat vertices and edges, and have any finite length. The hypothesis says: for all $i$ and $d$, if there is a walk from $i$ to $i$ of weight $d$, then $d\ge 0$. For $n=0$ there is exactly one (empty) instance.

Input encoding. The input is the list of integers consisting of

1. the $n\times n$ 0/1 adjacency matrix, row by row (entry $(i,j)$ is $1$ if there is an edge $i\to j$, else $0$), followed by
2. the $n\times n$ weight matrix, row by row (entry $(i,j)$ is $w(i,j)$ if there is an edge, else $0$).

So the input has length $2n^2$. The bound $|a|\le n^{\kappa}$ applies to every entry of this list (so to every edge weight; for $n=1$ it forces weights in $\{-1,0,1\}$, for $n=0$ the list is empty).

Machine model. Memory is a map from all integers (negative addresses included) to $W$-bit words. Initially cell $0$ holds $n$, cells $1,\dots,2n^2$ hold the input list in order, and every other cell (including all negative-address cells) holds $0$; each integer is stored as its $W$-bit two's-complement representation (i.e. reduced modulo $2^W$). Writing $[i]$ for the word in cell $i$, the instructions are:

• $[i]:=1$ (the only constant);
• $[i]:=[j]+[k]$, $[i]:=[j]-[k]$, $[i]:=[j]\cdot[k]$, all modulo $2^W$;
• load $[i]:=[[j]]$ and store $[[i]]:=[j]$, where a word used as an address is read as a signed ($W$-bit two's-complement) integer;
• conditional jump: if $[i]$, read as signed, is $<0$, go to position $\ell$, else continue;
• accept; reject.

The cell indices $i,j,k$ in instructions are fixed integers in the program text. Execution starts at position $0$; running past the end of the program counts as reject. "Halts within $t$ steps" means that an accept or reject is executed as one of the first $t$ steps, the halting step itself counted (so $t=0$ never suffices).

Required behaviour ("solves $x$ within $T(n)$ steps"). Starting from the initial memory above, $P$ halts within $T(n)$ steps, and:

• the verdict is accept (APSP's acceptance condition is the trivially true one, so the verdict must always be accept);
• reading the final memory cells as signed integers, with output position $a$ meaning cell $1+2n^2+a$: for every pair $(i,j)$, letting

$$\text{flag}=\text{out}\bigl(2(in+j)\bigr),\qquad \text{dist}=\text{out}\bigl(2(in+j)+1\bigr),$$

exactly one of the following holds (inclusive "or" of mutually exclusive cases):

• $\text{flag}=1$, there is a walk from $i$ to $j$ of weight exactly $\text{dist}$, and every walk from $i$ to $j$ has weight $\ge \text{dist}$ (so dist is the minimum walk weight); or
• $\text{flag}=0$ and there is no walk from $i$ to $j$ of any weight.

In particular, for $i=j$ the empty walk exists, so flag must be $1$ and dist the minimum closed-walk weight at $i$, which by the hypothesis is $0$. Output values must be representable as signed $W$-bit words to be read back correctly. No other memory cells are constrained.

Defined but unused. The imported file also defines, without being used by this statement: the problem ExactTriangle (three $n\times n$ integer matrices $w_{AB},w_{BC},w_{AC}$, input their row-by-row concatenation, accept iff some $a,b,c$ have $w_{AB}(a,b)+w_{BC}(b,c)+w_{AC}(a,c)=0$); the rational constant $\varepsilon_T=0.0017$; and the problem MinPlusProduct (two $n\times n$ integer matrices $A,B$; output cell $in+j$ must equal $\min_k (A(i,k)+B(k,j))$, phrased as attained by some $k$ and $\le$ every such sum; for $n=0$ vacuous). None of these enter the APSP statement.