P-sufficient statistics for PAC learning k-term-DNF formulas through enumeration

Working in the framework of PAC-learning theory, we present special statist ics for accomplishing in polynomial time proper learning of DNF boolean for mulas having a fixed number of monomials. Our statistics turn out to be nea r sufficient for a large family of distribution laws - that we call butterf ly distributions. We develop a theory of most powerful learning for analyzi ng the performance of learning algorithms, with particular reference to tra de-offs between power and computational costs. Focusing attention on sample and time complexity, we prove that our algorithm works as efficiently as t he best algorithms existing in the literature - while the latter only take care of subclasses of our family of distributions. (C) 2000 Elsevier Scienc e B.V. All rights reserved.