<p>This is a basic question, yet I tend to answer simple ones too :)</p>

<p>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:</p>

<p>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\}^∗$).</p>

<p>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.)</p>

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

<p>Needless to say, infinite functions have infinite size, unless you can compress the list somehow. (This brings up the "<a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow">Kolmogorov Complexity Theory</a>", which is a story for another day!)</p>

CC BY-SA 2.5
2010-10-05T12:13:10.953Z
Thank you very much for taking the time to answer this :) It will definitely help me to go on.
Felix
CC BY-SA 2.5
2010-10-05T12:20:50.673Z
Any time! Just make sure criticism does not prevent you from asking :)
Sadeq Dousti
CC BY-SA 2.5
2010-10-05T10:28:55.230Z
2010-10-05T10:49:51.777Z
2010-10-05T10:49:51.777Z
Sadeq Dousti
<p>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.</p>

<h2>Context</h2>

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

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

<h2>Question</h2>

<p>If the solution to a search problem is a function, how is the <em>size</em> of the function ($|y|$) determined? I thought, it could be size of the <em>input</em> of that function, but I am not sure.</p>

CC BY-SA 2.5
2010-10-05T09:21:19.653Z
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
CC BY-SA 2.5
2010-10-05T09:26:54.247Z
@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
CC BY-SA 2.5
2010-10-05T10:25:41.277Z
For what it’s worth, this question would be too basic on MathOverflow, too.  You might want to try at http://math.stackexchange.com/.
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes>
What is the size of a function?
Felix
# What is the size of a function?

(Asked by: username_0 on 2010-10-05)

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.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: 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)  
> **username_0**: @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?  
> **username_2**: For what it’s worth, this question would be too basic on MathOverflow, too.  You might want to try at http://math.stackexchange.com/.  

---

## 1 answers

### Answer by username_3 on 2010-10-05. Score: 6 | Accepted answer

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](http://en.wikipedia.org/wiki/Kolmogorov_complexity)", which is a story for another day!)

> **Comments:**
> **username_0**: Thank you very much for taking the time to answer this :) It will definitely help me to go on.  
> **username_3**: Any time! Just make sure criticism does not prevent you from asking :)  

---

