What is the size of a function? I'm not sure whether this question should be asked on mathoverflow.com or here, but as it is in the context of computational complexity, I will ask here.

Context

Oded Goldreich states in his book Computational Complexity: A Conceptual Perspective (no advertising intended!) that a search problem is in PC (Polynomial-Time Check) if it fulfills this condition among others:


  There exists a polynomial $p$ s.t. if $(x, y) \in R$ then $|y| \leq p(|x|)$.


Question

If the solution to a search problem is a function, how is the size of the function ($|y|$) determined? I thought, it could be size of the input of that function, but I am not sure.
This is a basic question, yet I tend to answer simple ones too :)

In the book you mentioned, take a look at section 1.2.1 (page 18). It describes how various objects are encoded. Among other things, it includes a section "Strings," in which "relation encoding" is described:

At times, we associate $\{0, 1\}^∗ \times \{0, 1\}^∗$ with $\{0, 1\}^∗$; the reader should merely consider an adequate encoding (e.g., the pair 
$(x_1 \dots x_m, y_1 \dots y_n) \in \{0, 1\}^∗ \times \{0, 1\}^∗$ 
may be encoded by the string $x_1x_1 \dots x_mx_m01y_1 \dots y_n \in \{0, 1\}^∗$).

Functions are a special type of relation, so they can be similarly encoded. In particular, a (finite and discrete) function can be seen as a list of input-output relations: $f=\{(x_1,y_1),\dots,(x_n,y_n)\}$. This can be easily encoded by incorporating a special symbol, say $\circ$. That is, $enc(f)=x_1 \circ y_1 \circ \dots \circ x_n \circ y_n$. (The encoding can be done without any special symbol, but it adds unnecessary intricacy.)

This way, the size of $f$ is the size of its encoding: $|enc(f)| \approx \sum_{i=1}^{n}{(|x_i|+|y_i|)}$.

Needless to say, infinite functions have infinite size, unless you can compress the list somehow. (This brings up the "Kolmogorov Complexity Theory", which is a story for another day!)