Publication Details
Title: On the Complexity of Genuinely Polynomial Computation
Author: M. Karpinski and F. M. auf der Heide
Group: ICSI Technical Reports
Date: January 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-04.pdf
Overview:
We present the separation results on genuinely (also called strong) sequential, parallel, and non-deterministic complexity classes for the set of arithmetic RAM operations {+, -, *} and {+, -, DIV subscript c}. In particular, we separate non-uniform polynomial time from non-uniform parallel polynomial time for the set of operations {+, -, *}, answering a question posed in [Meyer auf der Heide 88].
Bibliographic Information:
ICSI Technical Report TR-90-004
Bibliographic Reference:
M. Karpinski and F. M. auf der Heide. On the Complexity of Genuinely Polynomial Computation. ICSI Technical Report TR-90-004, January 1990
Author: M. Karpinski and F. M. auf der Heide
Group: ICSI Technical Reports
Date: January 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-04.pdf
Overview:
We present the separation results on genuinely (also called strong) sequential, parallel, and non-deterministic complexity classes for the set of arithmetic RAM operations {+, -, *} and {+, -, DIV subscript c}. In particular, we separate non-uniform polynomial time from non-uniform parallel polynomial time for the set of operations {+, -, *}, answering a question posed in [Meyer auf der Heide 88].
Bibliographic Information:
ICSI Technical Report TR-90-004
Bibliographic Reference:
M. Karpinski and F. M. auf der Heide. On the Complexity of Genuinely Polynomial Computation. ICSI Technical Report TR-90-004, January 1990