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

摘要

A monotone planar circuit (MPC) is a Boolean circuit that can be embedded in a plane, and that has only AND and OR gates. Yang showed that the one-input-face monotone planar circuit value problem (MPCVP) is in NC~2, and Limaye et. Al. improved the bound to LogCFL. Barrington et. Al. showed that evaluating monotone upward stratified circuits, a restricted version of the one-input-face MPCVP, is in LogDCFL. In this paper, we prove that the unrestricted one-input-face MPCVP is also in LogDCFL. We also show this problem to be L-hard under quantifier free projections.