The complexity of circuit value and network stability (Q1190989)

The circuit value problem over the basis \(\Omega\) (\(\Omega-CV\) for short) is the following: given a circuit \(C\) over the basis \(\Omega\) and an input vector \(x\), decide if \(C(x)=1\). The network stability problem, \(\Omega-NS\), is: given a circuit \(C\) over \(\Omega\), an input vector \(x\) and an assignment of values to the edges of \(C\), decide if this assignment is consistent with the computation of \(C\) on \(x\). The paper deals with the complexity of these two problems for various bases \(\Omega\). When fanout of the gates in \(\Omega\) are appropriately limited, some positive results are obtained: a parallel algorithm for \(\Omega-CV\) which runs in time about square root of the number of gates and a linear- time sequential algorithm for \(\Omega-NS\). Next, so called ``scatter- free'' bases are considered. These are bases all the gates in which have the following property: if we assign constants to any \(k\) inputs of the gate \(g(0\leq k\leq fanin(g))\), the new gate computes at most \(k\) different functions. It is proved that if \(\Omega\) is a scatter-free basis that can simulate the function \(\neg x\lor\neg y\) then \(\Omega-NS\) is equivalent to \(\Omega-CV\). The class \(CC\) of problems which are reducible to \(\Omega-CV\) when \(\Omega\) is the monotone scatter-free basis is considered. Obviously, \(CC\subseteq P\). It is proved that \(NL\subseteq CC\) and that a restricted version of the Maximal Matching problem is \(CC\)-complete.