I've always been curious about the feedback/loops restriction. Does anyone know how much things can be improved for boolean _functions_ that are implemented with feedback and/or loops? I suspect that latency can't be improved, but I suspect that the # of gates can be improved over the no feedback/loop version. (To be clear, I'm thinking about implementing functions using circuits that might have state, but the initial state is irrelevant to the output. For example, a boolean circuit might utilize some sort of hash table lookup to implement an initial guess that is verified before being output. In this case, the (mean) latency could be improved over the no-state version.) At 05:00 PM 12/29/2005, Schroeppel, Richard wrote:
The allowed gates are two-input And and two-input Xor; also, Nots may be used freely, and don't count against the total. As usual, the circuits must be DAGs (no feedback or loops), and circuit depth doesn't matter.