Learning conjunctions of two unate DNF formulas (extended abstract)
Aaron Feigelson, Lisa Hellerstein · 1996
We consider the class 77,2, consisting of conjunctions of two unate DNF formulas.This class is a generalization of the class of 2-clause CNF formulas, and of the class of unate DNF formulas, both of which are properly learnable in polynomial time with membership and equivalence queries.We show that 7?2 can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but that it cannot be learned in polynomial time unless P = NP.Thus the barrier to learning 7?,2is computational rather than informational,In proving our results, we use recent techniques developed for the membership and equivalence query model, as well as Bshout y's work on the monotone dimension.We pose some related open questions on learning DNF formulas of small monotone dimension.queries to learn the class) or whether it is computational (a