SEPARATION OF COMPLEXITY CLASSES IN KOIRANS WEAK MODEL

Authors
CUCKER F SHUB M SMALE S
Citation
F. Cucker et al., SEPARATION OF COMPLEXITY CLASSES IN KOIRANS WEAK MODEL, Theoretical computer science, 133(1), 1994, pp. 3-14
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
133
Issue
1
Year of publication
1994
Pages
3 - 14
Database
ISI
SICI code
0304-3975(1994)133:1<3:SOCCIK>2.0.ZU;2-I
Abstract
We continue the study of:complexity classes over the weak model introd uced by P. Koiran. In particular we provide several separations of com plexity classes, the most remarkable being the strict inclusion of P i n NP. Other separations concern classes defined by weak polynomial tim e over parallel or alternating machines as well as over nondeterminist ic machines whose guesses are required to be 0 or 1.