The equivalence of Horn and network complexity for Boolean functions

Summary We propose in this paper a logical complexity measure — Horn complexity — for Boolean functions which measures the minimal length of quasi-Horn definitions of such functions by propositional formulae. The interest for this complexity measure comes on the one hand from the observation that the satisfiability problem for Horn formulae is in P, on the other hand from a strong connection to Cook's problem. We show the proposed Horn complexity to be polynomially equivalent to network complexity and therefore to Turing complexity for Boolean functions.A preliminary version of this work has appeared in the Proceedings of the 5^th Scandinavian Logic Symposium, edited by B. Mayoh and F. Jensen, Aalborg University Press, Aalborg 1979