Nondeterminism within P

Jonathan F. Buss, Judy Goldsmith

Research output: Contribution to journalArticlepeer-review

160 Scopus citations

Abstract

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
Volume22
Issue number3
DOIs
StatePublished - 1993

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

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

Cite this