|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Lower Bounds for RAMs and Quantifier Elimination | | Miklos Ajtai
; | | Date: |
1 Jun 2013 | | 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}-1
brace$, the binary
functions $lfloor x/y
floor $ (with $lfloor x/0
floor =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 (log d)^{frac{1}{2}} (log log d)^{-1}$. | | Source: | arXiv, 1306.0153 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER