New problems complete for nondeterministic log space
From MaRDI portal
Publication:4109298
DOI10.1007/BF01683259zbMath0341.68035MaRDI QIDQ4109298
Neil D. Jones, William T. Laaser, Y. Edmund Lien
Publication date: 1976
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)
Related Items
Equivalence classes and conditional hardness in massively parallel computations, Gradually intractable problems and nondeterministic log-space lower bounds, An efficiently solvable graph partition problem to which many problems are reducible, Henkin quantifiers and complete problems, Solving linear equations parameterized by Hamming weight, An approximate max-flow min-cut relation for undirected multicommodity flow, with applications, The complexity of pure literal elimination, The complexity of intersecting finite automata having few final states, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, The complexity of searching implicit graphs, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, Classifying the computational complexity of problems, Symmetric space-bounded computation, Oracle branching programs and Logspace versus \(P^*\), The parallel complexity of finite-state automata problems, Knapsack problems for NL, Multihead two-way probabilistic finite automata, The complexity of searching succinctly represented graphs, Capturing complexity classes by fragments of second-order logic, The logic of constraint satisfaction, Correctness of linear logic proof structures is NL-complete, COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE, A very hard log-space counting class, Minimizing finite automata is computationally hard, Complexity of some problems in Petri nets, On the complexity of some problems on groups input as multiplication tables, Minimal and Hyper-Minimal Biautomata, On log-tape isomorphisms of complete sets, Unnamed Item, Unnamed Item, The complexity of weakly recognizing morphisms, Sorting, linear time and the satisfiability problem, Boundedness, empty channel detection, and synchronization for communicating finite automata, Linear connectivity problems in directed hypergraphs, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, Note on the complexity of Las Vegas automata problems, On the space and circuit complexity of parameterized problems: classes and completeness, The complexity of the satisfiability problem for Krom formulas, Complete problems in the first-order predicate calculus
Cites Work
- Space-bounded reducibility among combinatorial problems
- Complete problems for deterministic polynomial time
- Relationships between nondeterministic and deterministic tape complexities
- Optimization of LR(k) parsers
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- The complexity of theorem-proving procedures
- Unnamed Item
- Unnamed Item
- Unnamed Item
