Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-083 | 7th June 2013 20:06

Lower Bounds for RAMs and Quantifier Elimination


Authors: Miklos Ajtai
Publication: 7th June 2013 20:07
Downloads: 2730


For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, 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$, by performing the operations on all components simultaneously. These are essentially the arithmetic operations that can be performed on a RAM, with wordlength $n$, by a single instruction. We show that there exists an $\epsilon>0$ and a term (that is, an algebraic expression) $F(x,y)$ built up from the mentioned operations, with the only free variables $x,y$, such that if $G_{d}(y)$, $d=0,1,2,...$, is a sequence of terms, and for all $d=0,1,2,...$, ${\bf M}_{d}\models \forall x, [G_{d}(x)=0\leftrightarrow \exists y, F(x,y)=0]$, then for infinitely many integers $d$, the depth of the term $G_{d}$, that is, the maximal number of nestings of the operations in it, is at least $\epsilon (\log d)^{\frac{1}{2}}= \epsilon (\log \log n)^{\frac{1}{2}}$.

The following is a consequence. We are considering RAMs $N_{n}$, with wordlength $n=2^{d}$, whose arithmetic instructions are the arithmetic operations listed above, and also have the usual 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}\ge
(\log d)^{\frac{1}{2}-\epsilon}= (\log \log n)^{\frac{1}{2}-\epsilon}$.

ISSN 1433-8092 | Imprint