The Parallel Approximability of the False and True Gates Problems for NOR-Circuits
Marı́a Serna · Parallel Processing Letters · 2002
We study the parallel approximability of computing the number of true gates and false gates for circuits with only NOR gates, we refer to these problems as Nor-False Gates and Nor-True Gates Problems, respectively. We show that the parallel approximability of these problems depends on restrictions on the topology of the circuit. More precisely, for circuits with fan-in and fan-out bounded by a constant and having a constant number of output gates both problems exhibit a threshold behavior in their parllel approximability. Bounding only the number of outputs gives threshold results for the Nor-False Gates Problem but non-approximability (for any constant) for the Nor-True Gates Problem. For the case of unbounded number of outputs we show that none of the two problems can be approximated in parallel within any constant. We use the threshold result of False Gates Problem to identify a subclass of linear programming that also presents a threshold behavior in its parallel approximability.