On the Complexity of MAX/MIN/AVRG Circuits

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 concern this computation model, as well as its applications.