ECCC-Report TR11-102https://eccc.weizmann.ac.il/report/2011/102Comments and Revisions published for TR11-102en-usSun, 16 Jun 2013 22:26:13 +0300
Revision 1
| Determinism Versus Nondeterminism with Arithmetic Tests and Computation |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/2011/102#revision1For each natural number $d$ we consider a finite structure $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
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 $, $\max(x,y)$, $\min(x,y)$, and the
boolean vector operations $AND$, $OR$, $NEGATION$ 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 by a single instruction. We show that there
exists 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
for all terms $G(y)$, which is also built up from the mentioned
operations, the following holds. For infinitely many positive integers
$d$, there exists an $a\in M_{d}$ such that the following two statements
are not equivalent: (i) $M_{d} \models \exists x, F(x,a) $, (ii)
$M_{d}\models G(a)=0$. In other words, the question whether an
existential statement, depending on the parameter $a\in M_{d}$ is true
or not, cannot be decided by evaluating an algebraic expression at $a$.
We also show that this theorem remains true if we include the operation
$\min \lbrace x^{y}, 2^{n}-1 \rbrace$ into the structure $M_{d}$. A
general theorem is proved as well which describes sufficient conditions
for a set of operations on a sequence of structures $K_{d}$, $d=1,2,...$
which guarantees that the analogue of the mentioned theorem holds for
the structure $K_{d}$ too.Sun, 16 Jun 2013 22:26:13 +0300https://eccc.weizmann.ac.il/report/2011/102#revision1
Paper TR11-102
| Determinism Versus Nondeterminism with Arithmetic Tests and Computation |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/2011/102For each natural number $d$ we consider a finite structure $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
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 $, $\max(x,y)$, $\min(x,y)$, and the
boolean vector operations $AND$, $OR$, $NEGATION$ 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 by a single instruction. We show that there
exists 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
for all terms $G(y)$, which is also built up from the mentioned
operations, the following holds. For infinitely many positive integers
$d$, there exists an $a\in M_{d}$ such that the following two statements
are not equivalent: (i) $M_{d} \models \exists x, F(x,a) $, (ii)
$M_{d}\models G(a)=0$. In other words, the question whether an
existential statement, depending on the parameter $a\in M_{d}$ is true
or not, cannot be decided by evaluating an algebraic expression at $a$.
We also show that this theorem remains true if we include the operation
$\min \lbrace x^{y}, 2^{n}-1 \rbrace$ into the structure $M_{d}$. A
general theorem is proved as well which describes sufficient conditions
for a set of operations on a sequence of structures $K_{d}$, $d=1,2,...$
which guarantees that the analogue of the mentioned theorem holds for
the structure $K_{d}$ too.Sun, 31 Jul 2011 01:51:18 +0300https://eccc.weizmann.ac.il/report/2011/102