SIAM Journal on Computing · 1993 · 309 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationAutomata TheoryComplexity TheoryComputational ComplexityComputational Complexity ClassesFinite-state MachinesTime ComplexityComplexity ClassesNondeterminismNondeterministic ComplexityNondeterministic Turing Machines
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 codes68Q1568Q05Keywordsnondeterminismquasilinear timecomputational complexity
8
Satisfiability Is Quasilinear Complete in NQL
C. P. Schnorr · Journal of the ACM · 1978 · 82 citations · Full text
Classes of bounded nondeterminism
Jacobo Torán · Theory of Computing Systems · 1990 · 77 citations