[Solved]: The complexity class FP

Problem Detail: 

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?

Asked By : Uriel

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10886

3.2K people like this

 Download Related Notes/Documents