Exact learning when irrelevant variables abound

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.