[35] A Boolean formula is monotone if no literal in it is negated.

A k-term DNF is a DNF consisting of at most k monomials.

(a) Show that pac-learning monotone k-term DNF requires more than polynomial time unless RP=NP.

(b) Show that the class of monotone k-term DNF is polynomially paclearnable under m (even with the algorithm learning the exact concept with high probability).

Comments. This shows that more concepts are simple pac-learnable than are pac-learnable unless RP=NP. Source for Item (a): [L. Pitt and L.G.

Valiant, J. ACM, 35(1989), 965–984]; for Item (b): [M. Li and P.M.B.

Vit´anyi, SIAM J. Comput., 20:5(1991), 911–935].