Nondeterminism within $P^ * $ 论文
1993SIAM Journal on Computing引用 309
Computability, Logic, AI Algorithmssemigroups and automata theoryComplexity and Algorithms in Graphs
摘要
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