# What is the relevance of the concept size to the time constraints in PAC learning?

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)?

For example, you can represent the boolean parity function with a circuit composed of $$\land$$, $$\lor$$ and $$\neg$$ such that its size is polynomial in $$n$$, while, if you used a disjunctive normal form (DNF) representation, you might need an exponential number of terms. This may give you some intuition behind this example.
For some concept classes, $$\text{size}(c)$$ is already bounded by a polynomial in $$n$$, so the only practical requirement that you need in those cases is that the algorithm runs in time polynomial in $$n$$. For example, if you consider the class of DNF with at most 3 terms, then you know that the number of literals is at most $$3n$$ (i.e. each term can contain at most $$n$$ literals, either $$x_i$$ or $$\neg x_i$$ but not both, for all literals $$x_1, \dots, x_n$$).