Smale's ninth problem: no linear-time program

The mission's goal asserts the existence of a program $P$ and constants $C, d$ such that $P$ decides $\{x \mid Ax \ge b\} \ne \emptyset$ within $C\,(mn+m+2)^d$ steps for all $m$, $n$, $A$, $b$. This statement settles the case $d = 1$ negatively.

The assertion. For every program $P$ in the fixed instruction set of the mission's machine and every constant $C$, there are $m$, $n$, $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$ such that $P$, started on the standard encoding, does not halt with the correct verdict within $C\,(mn+m+2)$ steps.

Reading. The exponent $d$ in the goal is genuinely needed: no algorithm in this model runs in time linear in the number of input reals. The reason is the fixed-address structure of the machine: a single-variable instance places each coefficient $a_i$ exactly $m$ cells away from its right-hand side $b_i$, and the one-variable lower bound shows that a linear budget leaves too few boundary crossings to combine them. Taking $n = 1$, the input size is $2m + 2$, so a linear budget $C(mn+m+2)$ is a linear budget $2C(m+1)$ for the one-variable problem, which is excluded.

What it leaves open. Everything with $d \ge 2$. The mission's goal is the assertion that some $d$ works; this theorem only shows that $d = 1$ does not.