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
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1991.
Funding
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.
| Funders | Funder number |
|---|---|
| National Science Foundation (NSF) | RII-9003056 |
| Natural Sciences and Engineering Research Council of Canada |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science