一个概念类$C$如果存在至少可以输出概率假设的算法，那么是 PAC 可学习的$(1-\delta)$（“可能”部分），以及小于$\epsilon$（“大约”部分），在时间上是多项式的$1/\epsilon$,$1/\delta$,$n$和$|C|$.

Tom Mitchell定义了样本复杂度的上限，$m >= 1/\epsilon (ln(|H|) + ln(1/\delta))$对于有限假设。基于这个界限，他对目标概念是否是 PAC 可学习的进行分类。例如，$n$连词布尔字面量概念类。

在我看来，PAC-learnability 似乎更像是某些概念类的分类。

了解概念类是否可通过 PAC 学习是否有任何实际目的？