Feasible Real Functions and Arithmetic Circuits
H. James Hoover · SIAM Journal on Computing · 1990
The connection between computable analysis and computational complexity is investigated by asking what it means to feasibly compute a real function. A new class of arithmetic circuits, called feasible-size-magnitude, is introduced and used to show a feasible version of the Weierstrass approximation theorem. That is, a real function is feasible if and only if it can be sup-approximated by a division-free uniform family of feasible-size-magnitude arithmetic circuits over R. This result involves a counter-intuitive simulation of Boolean circuits by arithmetic ones. It also has implications for algebraic complexity theory.