scientific article; zbMATH DE number 3987266

zbMATH Open0611.03021MaRDI QIDQ3751569FDOQ3751569

Authors: Christoph Meinel 

Publication date: 1986

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 4041256
• scientific article
• 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\)

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)

Cited In (11)

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

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)