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 |