On the Complexity of Genuinely Polynomial Computation

TitleOn the Complexity of Genuinely Polynomial Computation
Publication TypeTechnical Report
Year of Publication1990
AuthorsKarpinski, M., & der Heide F. Meyer auf
Other Numbers568
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].

URLhttp://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