Relativization of questions about log space computability

DOI10.1007/BF01683260zbMath0341.68036OpenAlexW2015413218MaRDI QIDQ4109299

Publication date: 1976

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01683260

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Related Items (58)

Alternating and empty alternating auxiliary stack automata. ⋮ Census techniques collapse space classes ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)$\neq NSPACE(\log \,n)$ ⋮ Completeness for nondeterministic complexity classes ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Positive relativizations for log space computability ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ Decompositions of nondeterministic reductions ⋮ Relativized alternation and space-bounded computation ⋮ A time-space hierarchy between polynomial time and polynomial space ⋮ A measure of relativized space which is faithful with respect to depth ⋮ The logarithmic alternation hierarchy collapses: $A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}$ ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ On the complexity of graph reconstruction ⋮ Structure and importance of logspace-MOD class ⋮ Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Emptiness problems for integer circuits ⋮ The emptiness problem for intersections of regular languages ⋮ Empty alternation ⋮ RelativizedNC ⋮ Logics capturing relativized complexity classes uniformly ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Adaptive logspace reducibility and parallel time ⋮ New developments in structural complexity theory ⋮ Some results on relativized deterministic and nondeterministic time hierarchies ⋮ Space-efficient informational redundancy ⋮ On eliminating nondeterminism from Turing machines which use less than logarithm worktape space ⋮ On truth-table reducibility to SAT ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Complexity theory for splicing systems ⋮ An NL hierarchy ⋮ On quasilinear-time complexity theory ⋮ Computing functions with parallel queries to NP ⋮ A survey of space complexity ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ A very hard log-space counting class ⋮ On the autoreducibility of functions ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ A note on relativized log space ⋮ On expressive power of regular realizability problems ⋮ On relativizing auxiliary pushdown machines ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Unnamed Item ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Log space machines with multiple oracle tapes ⋮ On languages specified by relative acceptance ⋮ Planar and grid graph reachability problems ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ On the complexity of data disjunctions. ⋮ Consistency in nondeterministic storage ⋮ Space-bounded hierarchies and probabilistic computations ⋮ The relative power of logspace and polynomial time reductions ⋮ Relativizing small complexity classes and their theories

Cites Work

This page was built for publication: Relativization of questions about log space computability