My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions.
Definitions:
Define the input space as $X_n = {\left\{ 0,1\right\} }^n$ and a concept $c$ as a subset of $X_n$. For example, all vectorized images of size $n$ representing a particular numeral $i$ (e.g. '5') collectively form the concept $c_i$ for that numeral. A concept class $C_n$ is a set of concepts. Continuing our example, the vectorized numeral concept class $\left\{ c_0, c_1, \dots c_9\right\}$ is the set of all ten vectorized numeral concepts for a given dimension $n$.
As an extension to include all dimensions we define $\mathcal{C} = \cup_{n \geq 1} C_n$. A hypothesis set $H_n$ is also a fixed set of subsets of $X_n$ (which might not necessarily align with $C_n$) and we define $\mathcal{H} = \cup_{n \geq 1} H_n$.
The following definition of efficient PAC-learnability is adapted from An Introduction to Computational Learning Theory by Kearns and Vazirani.
$\mathcal{C}$ is efficiently PAC-learnable if there exists an algorithm $\mathcal{A}$ such that for all $n \geq 1,$ all concepts $c \in C_n$, all probability distributions $D$ on $X_n$, and all $\epsilon, \delta \in \left(0,1\right)$, the algorithm halts within polynomial time $p{\left( n, \text{size}{\left(c\right)}, \frac{1}{\epsilon}, \frac{1}{\delta}\right)}$ and returns a hypothesis $h \in H_n$ such that $$ \underset{x \sim D}{\mathbb{P}}{\left[ h{\left(x\right)} \neq c{\left(x\right)} \leq \epsilon\right]} \geq 1 - \delta.$$
Question:
Now, in the polynomial $p{\left(\cdot, \cdot, \cdot, \cdot \right)}$, I understand the dependence on $\epsilon$ (accuracy) and $\delta$ (confidence). Additionally, I understand why the polynomial should depend on $n$ - the concept of learnability should be invariant to the time burden incurred from increasing the dimension of the input space (e.g. increasing the resolution of the image). What I do not understand is why the dependence on the size of the target concept (which I believe is usually taken to mean the smallest encoding of the target concept)?
