Nondeterministic Space is Closed under Complementation
- 1 October 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (5) , 935-938
- https://doi.org/10.1137/0217058
Abstract
No abstract availableThis publication has 8 references indexed in Scilit:
- Symmetric space-bounded computationPublished by Elsevier ,2002
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- Symmetric ComplementationJournal of the ACM, 1984
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Classes of languages and linear-bounded automataInformation and Control, 1964