Lower Bounds for RAMs and Quantifier Elimination

Miklos Ajtai

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 functi…