Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | STACS 1991 - 8th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings |
| Editors | Christian Choffrut, Matthias Jantzen |
| Pages | 348-359 |
| Number of pages | 12 |
| DOIs | |
| State | Published - 1991 |
| Event | 8th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1991 - Hamburg, Germany Duration: Feb 14 1991 → Feb 16 1991 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 480 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 8th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1991 |
|---|---|
| Country/Territory | Germany |
| City | Hamburg |
| Period | 2/14/91 → 2/16/91 |
Bibliographical note
Funding 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.
Funding Information:
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.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)