
CMUCS02110
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS02110
On the Complexity of MAX/MIN/AVRG Circuits
Manuel Blum, Rache Rue, Ke Yang
March 2002
CMUCS02110.ps
CMUCS02110.pdf
Keywords: Circuits, complexity, NP, coNP, twoperson game
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 fanin 2; there
can be feedbacks 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
