Publication:3751569
From MaRDI portal
zbMath0611.03021MaRDI QIDQ3751569
Publication date: 1986
Turing machine; branching programs; graph accessibility problem; nonuniform complexity classes; logarithmic space complexity; p-projection reducibility
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Lower bounds for the modular communication complexity of various graph accessibility problems, Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree, The power of nondeterminism in polynomial-size bounded-width branching programs, Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits, A survey of space complexity, Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines