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

Read-back of TrulySubcubicAPSP.apsp_bound_299791. The theorem has no hypotheses or parameters. It says that the problem $\mathrm{APSP}$ (defined below) is solved in time exponent $r = 2.99791$, where $r$ is the exact rational number $\tfrac{299791}{100000}$ (already in lowest terms). It does this on the specific word-RAM model defined below. Written out in full, it asserts the following.

Statement. For every natural number $\kappa$ (the bound on the size of input numbers), there exist

• a program $P$, which is a finite list of instructions,
• a natural number $b$ (the word-size multiplier), and
• a function $T:\mathbb N\to\mathbb N$ (the time bound),

such that the following hold:

1. Time bound. There is a natural number $K$ with

$$T(n)^{100000} \le K\, n^{299791}\qquad\text{for all } n \ge 2.$$

This is the same as $T(n) \le K^{1/100000}\, n^{2.99791}$. Nothing is required of $T(0)$ or $T(1)$. 2. Correctness. Take any $n\in\mathbb N$ and any APSP instance $x$ on $n$ vertices whose input list (described below) has every entry $a$ satisfying $|a| \le n^{\kappa}$. Then for every word length $W$ with

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

the program $P$, run on $x$ with $W$-bit words, halts within $T(n)$ steps, accepts, and writes a correct output. Here $\lfloor\log_2 0\rfloor$ is taken to be $0$, so for $n \in \{0,1\}$ the condition is just $W \ge b$. The program $P$, the multiplier $b$ and the function $T$ may depend on $\kappa$. They may not depend on $n$, $x$ or $W$. In particular, the step bound $T(n)$ is the same for every allowed $W$.

The APSP instances. An instance on $n$ vertices is a function $w$ that assigns to each ordered pair $(i,j)$ of vertices in $\{0,\dots,n-1\}$ either "no edge" or an edge with an integer weight $w_{ij}\in\mathbb Z$. The graph is directed. Self-loops are allowed, and weights may be negative or zero.

A path from $i$ to $k$ of weight $d$ is defined as follows:

• the empty path from $i$ to $i$ has weight $0$;
• if there is an edge $i\to j$ of weight $d$ and a path from $j$ to $k$ of weight $e$, then there is a path from $i$ to $k$ of weight $d+e$.

So paths are arbitrary finite walks, and they may repeat vertices and edges. An instance must satisfy one side condition: every closed walk from a vertex $i$ back to $i$ has total weight $\ge 0$. In other words, there is no negative-weight cycle, and in particular every self-loop has weight $\ge 0$. The machine does not receive this condition; it only receives the input list.

Input encoding. The input list has length $2n^2$ and consists of two parts, in this order:

• the $n\times n$ $0/1$ adjacency matrix in row-major order (entry $1$ iff there is an edge $i\to j$);
• the $n\times n$ weight matrix in row-major order, with $0$ written for every absent edge.

The size hypothesis $|a|\le n^\kappa$ therefore bounds every edge weight by $n^\kappa$ in absolute value. For example, when $\kappa=0$ or $n=1$, every weight must lie in $\{-1,0,1\}$. When $n=0$ the input is empty, so the hypothesis holds vacuously.

Required behaviour. The APSP problem has no yes/no condition, so the verdict must always be "accept". Index the cells after the input by $a = 0,1,2,\dots$, so that output cell $a$ is memory cell $1+2n^2+a$. Each such cell is read as a signed $W$-bit integer. For every ordered pair $(i,j)$, let

$$f = \text{output cell } 2(in+j), \qquad \delta = \text{output cell } 2(in+j)+1.$$

Then exactly one of the following must hold:

• $f=1$, there is a path from $i$ to $j$ of weight exactly $\delta$, and every path from $i$ to $j$ has weight $\ge \delta$; or
• $f=0$, and there is no path from $i$ to $j$.

Because the empty path exists, the diagonal pairs $(i,i)$ must have $f=1$ and $\delta=0$. The value $\delta$ must equal the true distance as an integer, after being read back as a signed $W$-bit number.

The machine model. Memory is a function from all integers (including negative addresses) to $W$-bit words. At the start:

• cell $0$ holds $n$;
• cells $1,\dots,2n^2$ hold the input list;
• every other cell, including all negative ones, holds $0$.

Every value is stored after reduction modulo $2^W$ (two's-complement encoding). Execution starts at instruction position $0$. Every executed instruction, including the halting one, costs one step. The instruction set is listed below; $[c]$ denotes the word in cell $c$, and the cell indices $i,j,k$ are fixed integer constants written into the program.

• $[i] := 1$ (the only constant available);
• $[i] := [j]+[k]$, $[i] := [j]-[k]$, $[i] := [j]\cdot[k]$, all computed modulo $2^W$;
• load: $[i] := [[j]]$;
• store: $[[i]] := [j]$, where an address read from a word is interpreted as a signed integer;
• conditional jump: go to position $\ell$ if $[i]$ is negative as a signed word, and otherwise continue with the next instruction;
• accept;
• reject.

Running past the end of the program counts as a reject. The machine has no division, shifts, bitwise operations or comparison other than the sign test. "Halts within $t$ steps" means that an accept or a reject is executed within the first $t$ instructions; the verdict and the final memory are the ones at that moment. If the program does not halt within $t$ steps, the run does not count as solving the instance.

The imported file also defines Exact Triangle, the min-plus product and the constant $\varepsilon_T = 0.0017$. The theorem does not use any of them.