5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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) $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 5 '10 at 9:21
  • $\begingroup$ @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? $\endgroup$ – Felix Oct 5 '10 at 9:26
  • 2
    $\begingroup$ For what it’s worth, this question would be too basic on MathOverflow, too. You might want to try at math.stackexchange.com. $\endgroup$ – Tsuyoshi Ito Oct 5 '10 at 10:25
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.