1
$\begingroup$

I have a hard time understanding the following lines from our lecture notes:


$f \in \text{FP}$ iff there is a transducer T that computes $f$ and there exists a polynomial $p$ such that $TIME(T(x)) \leq p(|x|).$

Note: If $f \in \text{FP},$ then $|f(x)| \leq p(|x|)$ holds for a fixed polynomial $p.$

Examples:

$f(x) = x^2$ ($x$ is a binary number)

$f(x) = $ Table of the shortest paths from a start node s in a directed graph $G,$ where $G$ and $s$ are coded as $x.$

$f(x) = 2^x$ is not in $\text{FP}.$


Can somebody please explain the examples in a dummy-friendly way?

$\endgroup$
  • 2
    $\begingroup$ In a more informal way: $f \in FP$ if there is a Turing machine that on input $x$ (binary representation) write $f(x)$ (binary representation) on its output tape in polynomial time, i.e. in time $O( |x|^k)$ for some constant $k$ where $|x|$ is the length of the binary representation of $x$, i.e. $|x| = \lceil \log(x) \rceil$. $\endgroup$ – Vor Mar 29 '13 at 9:35
3
$\begingroup$

Recall that Turing Machines are often defined to output only a yes/no answer. Transducers are used to extend this to a general output, which is sometimes more appropriate for a certain task (e.g. defining mapping-reductions).

When we use transducers, we can also analyze their runtime, and in this case they compute functions, so we are interested in which functions can be computed using a transducer that runs in polynomial time.

In this context, running in polynomial time means that, as you state, the transducer is allowed to run for $p(|x|)$, where $p$ is a fixed polynomial, and $x$ is the input to the transducer. Finally, the transducer outputs the binary representation of the function that it computes.

Let's consider the first example: $f(x)=x^2$. A transducer that computes it takes as input a binary number, for example $11$ (3 in binary). It then needs to output $1001$. To actually compute this value, we can use the long-multiplication algorithm from preschool. What we need to notice is that this algorithm is indeed polynomial in $|x|$ - the length of the binary representation of $x$. It is not hard to verify that the algorithm runs in quadratic time of this length.

So we have a polynomial-time transducer for $f(x)=x^2$, so it is in FP.

Now let's consider example 3: $f(x)=2^x$. Consider an input $x$. What is the size of the binary representation of $f(x)$? Well, it's $\log f(x)$. But $$\log f(x)=\log 2^x=x$$ and $x$ is exponential in $|x|$ - indeed, the size of the representation of $x$ is $\log x$.

So we have that $\log(f(x))$ is exponential in $|x|$, or in other words, $|f(x)|$ is exponential in $|x|$, and in particular, $|f(x)|>|p(x)|$ for every polynomial $p$ and for large enough $x$ (because $2^n\in \omega(p(n))$ for every polynomial $p$).

So it is no possible to even write down $f(x)$ in polynomial time, let alone compute it. This is why $2^x\notin FP$.

Finally, the second example is just an emphasis on the relation between FP and P: Given $G,s$ in some representation (e.g. a "text file" encoded in binary) it is easy to compute the shortest path from $s$ to all the vertices using BFS, which runs in polynomial time. So essentially, once you run BFS on the graph and mark all the shortest paths, you get some binary string which represents it. You then output this binary string.

The important thing to take from the second example is the concept that if you are looking for a solution which is not a yes/no answer (e.g. shortest path, result of an arithmetic expression, etc.) and you can solve a related decision problem using TMs in polynomial time (e.g. "is there a path shorter than $k$?", "is the result of this expression smaller than $v$?"), then in many cases you can use the TM that solves the decision problems to actually obtain a transducer that runs in polynomial time, so the problem will be in FP.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer, Shaull. I think my main problem is still the idea behind the part $\leq p(|x|)$ of the definition. Consider again the first example: Our transducer T takes as input for example $11_2$ ($=3_{10}$) and it uses the long multiplication to produce the output $1001_2$ ($=9_{10}$). Questions: 1.) How do I know that the long multiplication is polynomial? 2.) The length $|11_2|$ is 2. This means that the function $p$ takes 2 as input, but how is this function $p$ defined; is it the long multiplication? $\endgroup$ – Uriel Mar 29 '13 at 14:36
  • 1
    $\begingroup$ Similarly to the class $P$, you need to have the runtime bound by some polynomial. Think about addition instead of multiplication: you get as input $x,y$ and need to compute $x+y$ (in binary). If you take a machine with 2 tapes, then addition requires one pass over the numbers, adding digit-by-digit, the same way a full-adder works. So the runtime would be linear (with 2 tapes) and this polynomial would be $O(n)$ (there is no point calculating it). Multiplication is more tricky, but if you analyze the algorithm, it is indeed polynomial. It is easy to bound it by $O(n^3)$, for example. $\endgroup$ – Shaull Mar 29 '13 at 14:44
  • 1
    $\begingroup$ First - you are right, the description length in binray of $x$ is $\lceil\log(x+1)\rceil$, and not $\log(x)$ as I wrote. To understand this, consider which numbers are represented with a string of length $k$: the maximal number that can be represented this way is $2^k-1$. This is because this number is $111...1$, whose value is $\sum_{i=0}^{k-1} 2^i=2^k-1$. Thus, if $x\le 2^k-1$, then the description length of $x$ is at most $k$, and by rearranging the equation we get $k\ge \log(x+1)$, and if $x>2^{k-1}$ then this length is at least $k-1$, since you have to have 1 in the MSB. $\endgroup$ – Shaull Mar 29 '13 at 15:30
  • 1
    $\begingroup$ I edited the answer. I hope it's clearer now. $\endgroup$ – Shaull Mar 29 '13 at 16:38
  • 1
    $\begingroup$ Good luck, and no sweat :) $\endgroup$ – Shaull Mar 29 '13 at 17:08

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.