We prove the following results. Any Boolean function of O(log n) relevant v
ariables can be exactly learned with a set of nonadaptive membership querie
s alone and a minimum sized decision tree representation of the function co
nstructed, in polynomial time. In contrast, such a function cannot be exact
ly learned with equivalence queries alone using general decision trees and
other representation classes as hypotheses.
Our results imply others which may be of independent interest. We show that
truth-table minimization of decision trees can be done in polynomial time,
complementing the well-known result of Masek that truth-table minimization
of DNF formulas is NP-hard. The proofs of our negative results show that g
eneral decision trees and related representations are not learnable in poly
nomial time using equivalence queries alone, confirming a folklore theorem.
(C) 1999 Elsevier Science B.V. All rights reserved.