LOOP CIRCUITS AND THEIR RELATION TO RAZBOROVS APPROXIMATION MODEL

Recently, a new technique called the method of approximations has been developed for proving lower bounds on the size of circuits computing certain Boolean functions. To obtain a lower bound on the size complex ity size(f) of a certain function f by the method, an appropriate legi timate model M for the function f is chosen, and then a lower bound on the distance rho(f, M) from f to M is derived. The lower bound on rho (f, M) becomes a lower bound on size( f) in view of the fact that size (f) greater than or equal to rho(f, M). Razborov gave a legitimate mon otone model, M(mon)(F-max), and showed that rho(f, M(mon)(F-max)) = Om ega(size(1/3)(f)), so there remains a gap between the size size(f) and the distance rho(f, M). Employing his method, the following statement s are established: (i) Razborov's model M(mon)(F-max) is generalized t o obtain model M(F-max), and it is established that rho(f, M(F-max)) = Omega(size(1/2)(f)). (ii) Allowing the underlying graphs of circuits to have cycles, a new notion of apparently more powerful circuits, cal led loop circuits, is introduced, and it is proved that rho(f, M(F-max ))=Theta(size(loop)(f)), where size(loop)(f) denotes the size complexi ty of f based on loop circuits. (C) 1995 Academic Press, Inc.