One-Input-Face MPCVP Is Hard for L, But in LogDCFL

DOI10.1007/11944836_8MaRDI QIDQ5385973zbMATH OpenOpenAlexFDO

Authors Tanmoy Chakraborty, Samir Datta

Publication date 17 April 2008

Published in FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

LLogDCFLmonotone planar circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Upper bounds for monotone planar circuit value and variants
• Evaluating Monotone Circuits on Cylinders, Planes and Tori
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• The monotone circuit value problem with bounded genus is in NC
• scientific article; zbMATH DE number 1003295

Cited in

(6)

• On the complexity of sandpile prediction problems
• A generalization of Spira's theorem and circuits with small segregators or separators
• A generalization of Spira's theorem and circuits with small segregators or separators
• Upper bounds for monotone planar circuit value and variants
• Evaluating monotone circuits on surfaces
• Planar and grid graph reachability problems

This page was built for publication: One-Input-Face MPCVP Is Hard for L, But in LogDCFL

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