Probably approximately correct learning (PAC learning) is a learning model
proposed by Leslie Valiant that introduces the concepts of computational
complexity to machine learning. In particular, given positive and negative
samples, the learner is expected to find a polynomial-time computable
function that could approximately distinguish between positive and negative
In this work, we study the PAC-learnability of DFAs, i.e., the case where
positive and negative samples are drawn from an unknown DFA. We show that,
unless NP=RP, DFAs are not PAC-learnable, thus, answering an open question
raised 25 years ago by Pitt and Warmuth.
This is a joint work with Parinya Chalermsook and Danupon Nanongkai.