In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits with \(\wedge ,\vee \) but no negation gates) that are embedded on a surface of bounded genus, and all inputs to the circuits lie on bounded number of input faces. We show that this problem belongs to complexity class \(\textsf{LogDCFL}\) . This along with the result of Cook [7], yields a simultaneously space-efficient ( \(O(\log ^2{n})\) -space) and polynomial time algorithm for the problem. It also gives a highly parallel algorithm (simultaneously \(O(\log {n})\) -time with polynomially many processors). This generalises the previous bound of \(\textsf{LogDCFL}\) for the problem on one input face monotone planar circuits [6]. More precisely, we show that if a monotone circuit is embedded on a surface of polylogarithmic genus g and has k faces on which all the inputs are present, then the circuit can be evaluated on a \(\textsf{CROW}\) -PRAM (concurrent read owner write parallel random access machine) in time \(O(g\log {(k+g)} \log {n})\) using \(n^{O(1)}\) many processors. We introduce a new distance metric in single sink DAGs that can be computed in deterministic logarithmic space ( \(\textsf{L}\) ) and is useful in partitioning the circuit into subcircuits such that each one is a one-input face monotone planar circuit. We also show that the partitioning procedure is done in deterministic logarithmic space. Thus we are able to side-step the barrier of computing the usual distance in bounded genus graphs, for which the best bound known is \(\textsf{UL}\,\cap \, \textsf{coUL}\) [18, 29] and therefore not known to be contained in \(\textsf{LogDCFL}\) . We also non trivially modify the parallel algorithm by Delcher-Kosaraju [9] for \(\textsf{MPCVP}\) to reduce the dependence of the parallel running time on the number of input faces from linear to logarithmic.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Evaluating Monotone Circuits on Surfaces

  • Samir Datta,
  • Chetan Gupta

摘要

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits with \(\wedge ,\vee \) but no negation gates) that are embedded on a surface of bounded genus, and all inputs to the circuits lie on bounded number of input faces. We show that this problem belongs to complexity class \(\textsf{LogDCFL}\) . This along with the result of Cook [7], yields a simultaneously space-efficient ( \(O(\log ^2{n})\) -space) and polynomial time algorithm for the problem. It also gives a highly parallel algorithm (simultaneously \(O(\log {n})\) -time with polynomially many processors). This generalises the previous bound of \(\textsf{LogDCFL}\) for the problem on one input face monotone planar circuits [6]. More precisely, we show that if a monotone circuit is embedded on a surface of polylogarithmic genus g and has k faces on which all the inputs are present, then the circuit can be evaluated on a \(\textsf{CROW}\) -PRAM (concurrent read owner write parallel random access machine) in time \(O(g\log {(k+g)} \log {n})\) using \(n^{O(1)}\) many processors. We introduce a new distance metric in single sink DAGs that can be computed in deterministic logarithmic space ( \(\textsf{L}\) ) and is useful in partitioning the circuit into subcircuits such that each one is a one-input face monotone planar circuit. We also show that the partitioning procedure is done in deterministic logarithmic space. Thus we are able to side-step the barrier of computing the usual distance in bounded genus graphs, for which the best bound known is \(\textsf{UL}\,\cap \, \textsf{coUL}\) [18, 29] and therefore not known to be contained in \(\textsf{LogDCFL}\) . We also non trivially modify the parallel algorithm by Delcher-Kosaraju [9] for \(\textsf{MPCVP}\) to reduce the dependence of the parallel running time on the number of input faces from linear to logarithmic.