### Boolean Formulas Are Hard to Learn for Most Gate Bases

**Author: Victor Dalmau**.

**Source: ***Lecture Notes in Artificial Intelligence* Vol. 1720,
1999, 301 - 312.

Boolean formulas are known not to be PAC-predictable even
with membership queries under some cryptographic
assumptions. In this paper, we study
the learning complexity of some subclasses of boolean formulas
obtained by varying the basis of elementary operations allowed
as connectives. This broad family of classes includes, as a particular
case, general boolean formulas, by considering the basis given by
{AND,OR,NOT}. We completely solve the
problem. We prove the following *dichotomy theorem*: For
any set of basic boolean functions, the resulting set of formulas is
either polynomially learnable from equivalence queries or membership
queries alone or else it is not PAC-predictable even with membership
queries under cryptographic assumptions. We
identify precisely which sets of basic functions are in which
of the two cases. Furthermore, we prove than the learning complexity
of formulas over a basis depends only on the absolute expressivity
power of the class, ie., the set of functions that can be represented
regardless of the size of the representation. In consequence, the
same classification holds for the learnability of boolean circuits.

©Copyright 1999 Springer-Verlag