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

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 Notes

ICSI Technical Report TR-90-004

Abbreviated Authors

M. Karpinski and F. M. auf der Heide

ICSI Publication Type

Technical Report