Computational Complexity of the Circuit Value and Network Stability Problems

摘要

This dissertation investigates the computational complexity of the Circuit Valueproblem and a new problem, Network Stability, when fanout is limited. In the Circuit Value problem, the task is to determine the ouput of an acyclic circuit of boolean gates. The Network Stability problem asks whether it is possible to assign values to the edges of a (possibly cyclic) network of boolean gates in a manner consistent with a given input assignment. Fanout is limited in a nontrivial way by allowing gates to have many outputs and then placing conditions on the different outputs produced by any single gate of the circuit or network. The fanout-limited versions of Circuit Value and Network Stability define new classes of problems between the standard Logarithmic-space and Polynomial-time complexity classes. The simplest of the new classes, CC, contains natural complete problems, including Circuit Value for Comparator Circuits and the Stable Matching (Stable Marriage and Stable Roomates) problems. One offshoot of this research is a fruitful new approach to the Stable Matching problems. Several positive results emerge when fanout is appropriately limited, including a parallel algorithm for Circuit Value, a linear-time sequential for Network Stability, a characterization of the networks that lack consistent assignments of values to edges, and equivalence of Circuit Value and Network Stability under logarithmic-depth reductions.