scientific article; zbMATH DE number 3987266

MaRDI QIDQ3751569zbMATHFDO

Authors Christoph Meinel

Publication date 1986

zbMATH Keywords

Turing machinebranching programsgraph accessibility problemnonuniform complexity classeslogarithmic space complexityp-projection reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 4041256
• scientific article; zbMATH DE number 4209586
• scientific article; zbMATH DE number 3904572
• The power of nondeterminism in polynomial-size bounded-width branching programs
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

Cited in

(11)

• Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
• A survey of space complexity
• \textsc{ReachFewL} = \textsc{ReachUL}
• Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
• The power of nondeterminism in polynomial-size bounded-width branching programs
• Gradually intractable problems and nondeterministic log-space lower bounds
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• scientific article; zbMATH DE number 17815 (Why is no real title available?)
• scientific article; zbMATH DE number 4085027 (Why is no real title available?)
• Lower bounds for the modular communication complexity of various graph accessibility problems
• scientific article; zbMATH DE number 3976381 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751569)