1993/06/01 by Jonathan F. Buss, Judy Goldsmith · 3 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #semigroups and automata theory #Complexity and Algorithms in Graphs #Combinatorics #Complexity class #Mathematics #NP-complete #Computer science #Discrete mathematics #Time complexity
paper · doi:10.1137/0222038
openalex publication_date 1993/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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. MSC codes 68Q15 68Q05 Keywords nondeterminism quasilinear time computational complexity