Name
Abstract | ||
|---|---|---|
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 NC2, and Limaye et. al. improved the bound to LogCFL. Barrington et. al. showed that evaluating monotone upward stratified cir- cuits, 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11944836_8 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
logdcfl,stratified circuit,barrington et,one-input-face monotone planar circuit,value problem,l,monotone planar circuit,boolean circuit,one-input-face mpcvp,quantifier free projection,monotone planar circuits.,unrestricted one-input-face,limaye et | Discrete mathematics,Combinatorics,Boolean circuit,Logic gate,LOGCFL,Planar,OR gate,Boolean algebra,Electronic circuit,Monotone polygon,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 130 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-49994-6 | 9 | 0.58 |
References | Authors | |
11 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tanmoy Chakraborty | 1 | 466 | 76.71 |
| Samir Datta | 2 | 200 | 19.82 |