Space-bounded reducibility among combinatorial problems

DOI10.1016/S0022-0000(75)80050-XzbMath0317.02039MaRDI QIDQ1221749

Publication date: 1975

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

68Q25: Analysis of algorithms and problem complexity

03D99: Computability and recursion theory

03D10: Turing machines and related notions

Related Items

Computational complexity of some problems involving congruences on algebras, Knapsack problems for NL, Multihead two-way probabilistic finite automata, On the equivalence of recursive and nonrecursive Datalog programs, Methods for proving completeness via logical reductions, Rewriting of regular expressions and regular path queries, Minimizing finite automata is computationally hard, On the complexity of topological sorting, Prediction-preserving reducibility, Bandwidth constraints on problems complete for polynomial time, The complexity of two-player games of incomplete information, Infinity problems and countability problems for \(\omega \)-automata, The complexity of pure literal elimination, Endmarkers can make a difference, Parallel models of computation: An introductory survey, Linear connectivity problems in directed hypergraphs, Complete problems for space bounded subclasses of NP, An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines, Simultaneous (poly-time, log-space) lower bounds, Alternating multihead finite automata, Characterization of idempotent transformation monoids, Problems concerning fairness and temporal logic for conflict-free Petri nets, Tree-size bounded alternation, The complexity of decision problems for finite-turn multicounter machines, Number of quantifiers is better than number of tape cells, Symmetric space-bounded computation, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, On the computational complexity of satisfiability in propositional logics of programs, Unifiability is complete for co-N Log Space, A note on the space complexity of some decision problems for finite automata, Iterated stack automata and complexity classes, Oracle branching programs and Logspace versus \(P^*\), The complexity of circuit value and network stability, A very hard log-space counting class, Polynomial and abstract subrecursive classes, Complete problems for deterministic polynomial time, The polynomial-time hierarchy, Complexity of some problems in Petri nets, Corrigendum: Space-bounded reducibility among combinatorial problems, Complete sets and the polynomial-time hierarchy, On inverse deterministic pushdown transductions, On the complexity of some two-person perfect-information games, On languages specified by relative acceptance, On log-tape isomorphisms of complete sets, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, The relative power of logspace and polynomial time reductions, On path equivalence of nondeterministic finite automata, Counting quantifiers, successor relations, and logarithmic space, On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\), A recognition and parsing algorithm for arbitrary conjunctive grammars., Complexity of path discovery game problems, Sorting, linear time and the satisfiability problem, Domino-tiling games, The complexity of propositional linear temporal logics in simple cases, Concurrent reachability games, The role of rudimentary relations in complexity theory, Note on the complexity of Las Vegas automata problems, The Simple Reachability Problem in Switch Graphs, Descriptional and Computational Complexity of Finite Automata, Gradually intractable problems and nondeterministic log-space lower bounds, Classifying the computational complexity of problems, A note on context free languages, complexity classes, and diagonalization, Completeness for nondeterministic complexity classes, Unnamed Item, New problems complete for nondeterministic log space, Relativization of questions about log space computability, The complexity of the membership problem for some extensions of context-free languagest†

Cites Work