Given a definition of error, we can now define PAC
learnability.
A concept class $C$ is
PAC-learnable by $L$ using
$H$ if for all $c \in C$, distributions $\cal{D}$ over $X$,
$\epsilon$ such that $0 < \epsilon < 1/2$, and
$\delta$ such that $0 < \delta < 1/2$, learner $L$
will with probability at least $(1-\delta)$ output a
hypothesis $h \in H$ such that $error_{\cal{D}}(h) \leq
\epsilon$, in time that is polynomial in $1/\epsilon$,
$1/\delta$, $n$ and $size(c)$.
Notice that even thought we only mention computation time,
computation time grows with the number of examples
needed.
So, we want to PAC-learn some concept, but when can we do it?