Pages that link to "Item:Q3821586"
From MaRDI portal
The following pages link to Nondeterministic Space is Closed under Complementation (Q3821586):
Displayed 50 items.
- A communication hierarchy of parallel computations (Q1129258) (← links)
- An NL hierarchy (Q1182111) (← links)
- On ``inherently context-sensitive'' languages -- an application of complexity cores (Q1183427) (← links)
- Oracle branching programs and Logspace versus \(P^*\) (Q1183604) (← links)
- The parallel complexity of finite-state automata problems (Q1186807) (← links)
- The complexity of circuit value and network stability (Q1190989) (← links)
- The invariant problem for binary string structures and the parallel complexity theory of queries (Q1191022) (← links)
- Capturing complexity classes by fragments of second-order logic (Q1193408) (← links)
- A survey of space complexity (Q1193412) (← links)
- On space-bounded synchronized alternating Turing machines (Q1193901) (← links)
- A lower bound for the nondeterministic space complexity of context-free recognition (Q1198017) (← links)
- The parallel complexity of coarsest set partition problems (Q1198030) (← links)
- Using the Hamiltonian path operator to capture NP (Q1198664) (← links)
- A very hard log-space counting class (Q1208403) (← links)
- On read-once vs. multiple access to randomness in logspace (Q1208412) (← links)
- Bridging across the \(\log(n)\) space frontier (Q1271619) (← links)
- On the power of built-in relations in certain classes of program schemes (Q1277684) (← links)
- Positive versions of polynomial time (Q1281503) (← links)
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis (Q1288202) (← links)
- Succinctness as a source of complexity in logical formalisms (Q1302307) (← links)
- The alternation hierarchy for sublogarithmic space is infinite (Q1312177) (← links)
- Context-sensitive transitive closure operators (Q1319508) (← links)
- Logical and schematic characterization of complexity classes (Q1323362) (← links)
- The complexity of optimizing finite-state transducers (Q1329734) (← links)
- Census techniques collapse space classes (Q1332770) (← links)
- Deterministic versus nondeterministic space in terms of synchronized alternating machines (Q1334670) (← links)
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization (Q1362330) (← links)
- Separating classes in the exponential-time hierarchy from classes in PH (Q1365687) (← links)
- Reachability and the power of local ordering (Q1367543) (← links)
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction (Q1390864) (← links)
- On the parallel complexity of loops (Q1391751) (← links)
- Space hierarchy theorem revised. (Q1401238) (← links)
- The complexity of the characteristic and the minimal polynomial. (Q1401240) (← links)
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits (Q1566723) (← links)
- A space lower bound for \(st\)-connectivity on node-named JAGs (Q1566733) (← links)
- A variant of inductive counting (Q1566745) (← links)
- Resolution of Hartmanis' conjecture for NL-hard sparse sets (Q1575434) (← links)
- A note on closure properties of logspace MOD classes (Q1583060) (← links)
- Decision algorithms for multiplayer noncooperative games of incomplete information (Q1609052) (← links)
- Hierarchical information and the synthesis of distributed strategies (Q1629748) (← links)
- Separability by piecewise testable languages is \textsc{PTime}-complete (Q1698734) (← links)
- Catalytic space: non-determinism and hierarchy (Q1702851) (← links)
- On the computational complexity of problems related to distinguishability sets (Q1706155) (← links)
- Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs (Q1729688) (← links)
- Complexity of deciding detectability in discrete event systems (Q1797011) (← links)
- Sorting, linear time and the satisfiability problem (Q1817067) (← links)
- Logic, semigroups and automata on words (Q1817074) (← links)
- Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space (Q1825656) (← links)
- For completeness, sublogarithmic space is no space. (Q1853022) (← links)
- The complexity of the exponential output size problem for top-down and bottom-up tree transducers (Q1854455) (← links)