Lower bounds for RAMs and quantifier elimination

DOI10.1145/2488608.2488710MaRDI QIDQ5495851zbMATH OpenOpenAlexFDO

Authors Miklós Ajtai

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.0153

zbMATH Keywords

diagonalizationlower boundsnondeterministic computationquantifier eliminationRAM

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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 $minlbrace{2}^x,2^n-1brace$, the binary functions $lfloorx/yfloor$ (with $lfloorx/0floor=0$), $max(x,y)$, $min(x,y)$, and the boolean vector operations $wedge,vee,eg$ 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(logd{)}^{frac12}(loglogd{)}^{-1}$.

Recommendations

• Lower bounds on algebraic random access machines
• Topological lower bounds on algebraic random access machines
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
• scientific article; zbMATH DE number 512978

Cited in

(6)

• Topological lower bounds on algebraic random access machines
• scientific article; zbMATH DE number 7228403 (Why is no real title available?)
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
• Lower bounds on algebraic random access machines
• Characterizing polynomial Ramsey quantifiers
• On O(Tlog T) reduction from RAM computations to satisfiability

This page was built for publication: Lower bounds for RAMs and quantifier elimination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495851)