Nondeterministic Space is Closed under Complementation

1988/10/01 by Neil Immerman · 9 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Optimization and Search Problems

paper · doi:10.1137/0217058

openalex publication_date 1988/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/09

Abstract

In this paper we show that nondeterministic space s(n) is closed under complementation for s(n) greater than or equal to log n. It immediately follows that the context-sensitive languages are closed under complementation, thus settling a question raised by Kuroda [Inform. and Control, 7 (1964), pp. 207–233].

Citations

• Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

Cited by

• Computation in networks of passively mobile finite-state sensors
• Describing Graphs: A First-Order Approach to Graph Canonization
• The Nature of Computation
• Two-Way Finite Automata: Old and Recent Results
• Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems
• Finite-model theory - a personal perspective
• Context-sensitive language [wikipedia]
• Descriptive complexity theory [wikipedia]
• Fixed-point logic [wikipedia]