Nondeterminism within P

Jonathan F. Buss, Judy Goldsmith

Research output: Contribution to journalArticlepeer-review

160 Scopus citations


Classes of machines using very limited amounts of nondeterminism are studied. The P =? NP question in related to questions about classes lying within P. Complete sets for these classes are given.

Original languageEnglish
Pages (from-to)560-572
Number of pages13
JournalSIAM Journal on Computing
Issue number3
StatePublished - 1993

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Nondeterminism within P'. Together they form a unique fingerprint.

Cite this