Nondeterminism within $P^ * $

Jonathan F. Buss, Judy Goldsmith

SIAM Journal on Computing · 1993 · 309 citations · 8 references

Concepts

Abstract

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

References

8