Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ARITHMETIC TEST:
Reports tagged with arithmetic test:
TR11-102 | 31st July 2011
Miklos Ajtai

Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revisions: 1

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




ISSN 1433-8092 | Imprint