AN NC ALGORITHM FOR EVALUATING MONOTONE PLANAR CIRCUITS

Goldschlager first established that a special case of the monotone pla nar circuit problem can be solved by a Turing machine in O(log(2)n) sp ace. Subsequently, Dymond and Cook refined the argument and proved tha t the same class can be evaluated in O(log(2)n) time with a polynomial number of processors. In this paper, we prove that the general monoto ne planar circuit value problem can be evaluated in O (log(4)n) time w ith a polynomial number of processors, settling an open problem posed by Goldschlager and Parberry.