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.

• Markus?! ;) Anyway, the question is really too basic here. (but: y is just a string. It could be encoding a function or anything else for that matter) – Kristoffer Arnsfelt Hansen Oct 5 '10 at 9:21
• @Kristoffer: Ups, I wanted to verify the name first ;) Yeah it is probably too basic, sorry for that. What would be the place to ask such questions? – Felix Oct 5 '10 at 9:26
• For what it’s worth, this question would be too basic on MathOverflow, too. You might want to try at math.stackexchange.com. – Tsuyoshi Ito Oct 5 '10 at 10:25

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

• Thank you very much for taking the time to answer this :) It will definitely help me to go on. – Felix Oct 5 '10 at 12:13
• Any time! Just make sure criticism does not prevent you from asking :) – M.S. Dousti Oct 5 '10 at 12:20