Back to Search
Start Over
Separation of complexity classes in Koiran's weak model
- 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