ON THE LEARNABILITY OF DISJUNCTIVE NORMAL-FORM FORMULAS

We present two related results about the learnability of disjunctive n ormal form (DNF) formulas. First we show that a common approach for le arning arbitrary DNF formulas requires exponential time. We then contr ast this with a polynomial time algorithm for learning ''most'' (rathe r than all) DNF formulas. A natural approach for learning boolean func tions involves greedily collecting the prime implicants of the hidden function. In a seminal paper of learning theory, Valiant demonstrated the efficacy of this approach for learning monotone DNF, and suggested this approach for learning DNF. Here we show that no algorithm using such an approach can learn DNF in polynomial time. We show this by con structing a counterexample DNF formula which would force such an algor ithm to take exponential time. This counterexample seems to capture mu ch of what makes DNF hard to learn, and thus is useful to consider whe n evaluating the run-time of a proposed DNF learning algorithm. This h ardness result, as well as other hardness results for learning DNF, re lies on the construction of particular hard-to-learn formulas, formula s that appear to be relatively rare. This raises the question of wheth er most DNF formulas are learnable. For certain natural definitions of ''most DNF formulas,'' we answer this question affirmatively.