We study the complexity of a class of circuits, namely, the MAX/MIN/AVRG circuits. On the wires of these circuits are real values between 0 and 1; the functions each gate performs are MAX, MIN, and AVERAGE of fan-in 2; there can be feed-backs in the circuit. It can be shown that every such circuit has at least a "stable" solution, meaning that there is a way to set each wire to a particular value such that each gate is satisfied. However, finding a stable solution in polynomial time seems to be a tricky problem and remains unsolved. We discuss some results concerning this computation model, as well as its applications.

31 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu