Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, Abt. V
8545

On the Complexity of Genuinely Polynomial Computation
Marek Karpinski, Friedhelm Meyer auf der Heide
[Download PostScript] [Download PDF]

We present separation results on genuinely (or strongly) time bounded sequential, parallel and non-deterministic complexity classes defined by RAMs with fixed set of arithmetic operations. In particular, we separate non-uniform polynomial time from non-uniform parallel polynomial time for the set of operations $\{+,-,*\}$ (answering a question of \cite{M 88}), and uniform deterministic polynomial time from uniform non-deterministic polynomial time for the set of operations $\{+,-,{\mathit DIV}_c\}$, where {\it DIV}$_c$ denotes a restricted integer division operation.

Last Change: 08/18/99 at 13:00:38
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope