Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR11-102 | 16th June 2013 22:26

#### Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revision #1
Authors: Miklos Ajtai
Accepted on: 16th June 2013 22:26
Keywords:

Abstract:

For 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.

### Paper:

TR11-102 | 31st July 2011 01:50

#### Determinism Versus Nondeterminism with Arithmetic Tests and Computation

TR11-102
Authors: Miklos Ajtai
Publication: 31st July 2011 01:51
Keywords:

Abstract:

For 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.

ISSN 1433-8092 | Imprint