scientific article; zbMATH DE number 3987266

zbMATH Open0611.03021MaRDI QIDQ3751569FDOQ3751569

Christoph Meinel

Publication date: 1986

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

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 (9)

• 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
• 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

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The power of nondeterminism in polynomial-size bounded-width branching programs 👍 👎
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) 👍 👎

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)