On the Complexity of Genuinely Polynomial Computation
Title | On the Complexity of Genuinely Polynomial Computation |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Karpinski, M., & der Heide F. Meyer auf |
Other Numbers | 568 |
Abstract | 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]. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-04.pdf |
Bibliographic Notes | ICSI Technical Report TR-90-004 |
Abbreviated Authors | M. Karpinski and F. M. auf der Heide |
ICSI Publication Type | Technical Report |