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