Classes of machines using very limited amounts of nondeterminism are studied. The P=? NP question is related to questions about classes lying within P. Complete sets for these classes are given.
|Title of host publication||STACS 1991 - 8th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings|
|Editors||Christian Choffrut, Matthias Jantzen|
|Number of pages||12|
|State||Published - 1991|
|Event||8th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1991 - Hamburg, Germany|
Duration: Feb 14 1991 → Feb 16 1991
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||8th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1991|
|Period||2/14/91 → 2/16/91|
Bibliographical noteFunding Information:
2Supported in part by National Science Foundation grant number RII-9003056. Much of this work done while a postdoe at Dartmouth College. Current address: Department of Computer Science, Boston University, Boston MA 02215, U.S.A.
1Supported in part by a grant from the Natural Sciences and Engineering Research Council (NSERC) of Canada. Author's address: Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1.
© Springer-Verlag Berlin Heidelberg 1991.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)