  We are considering RAMs $N_{n}$, with wordlength $n=2^{d}$, whose arithmetic
instructions are the arithmetic operations multiplication and addition modulo
$2^{n}$, the unary function $ \min\lbrace 2^{x}, 2^{n}-1\rbrace$, the binary
functions $\lfloor x/y\rfloor $ (with $\lfloor x/0 \rfloor =0$), $\max(x,y)$,
$\min(x,y)$, and the boolean vector operations $\wedge,\vee,\neg$ defined on
$0,1$ sequences of length $n$. It also has the other RAM instructions. The size
of the memory is restricted only by the address space, that is, it is $2^{n}$
words. The RAMs has a finite instruction set, each instruction is encoded by a
fixed natural number independently of $n$. Therefore a program $P$ can run on
each machine $N_{n}$, if $n=2^{d}$ is sufficiently large. We show that there
exists an $\epsilon>0$ and a program $P$, such that it satisfies the following
two conditions.
  (i) For all sufficiently large $n=2^{d}$, if $P$ running on $N_{n}$ gets an
input consisting of two words $a$ and $b$, then, in constant time, it gives a
$0,1$ output $P_{n}(a,b)$.
  (ii) Suppose that $Q$ is a program such that for each sufficiently large
$n=2^{d}$, if $Q$, running on $N_{n}$, gets a word $a$ of length $n$ as an
input, then it decides whether there exists a word $b$ of length $n$ such that
$P_{n}(a,b)=0$. Then, for infinitely many positive integers $d$, there exists a
word $a$ of length $n=2^{d}$, such that the running time of $Q$ on $N_{n}$ at
input $a$ is at least $\epsilon (\log d)^{\frac{1}{2}} (\log \log d)^{-1}$.
