Back to Search Start Over

Separation of complexity classes in Koiran's weak model

Authors :
Felipe Cucker
Steve Smale
Michael Shub
Source :
Theoretical Computer Science. 133(1):3-14
Publication Year :
1994
Publisher :
Elsevier BV, 1994.

Abstract

We continue the study of complexity classes over the weak model introduced by P. Koiran. In particular we provide several separations of complexity classes, the most remarkable being the strict inclusion of P in NP. Other separations concern classes defined by weak polynomial time over parallel or alternating machines as well as over nondeterministic machines whose guesses are required to be 0 or 1.

Details

ISSN :
03043975
Volume :
133
Issue :
1
Database :
OpenAIRE
Journal :
Theoretical Computer Science
Accession number :
edsair.doi.dedup.....a61a948bc0298dab98d619d9565f44e8
Full Text :
https://doi.org/10.1016/0304-3975(94)00069-7