Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with $FP_{0,1}$ and the class of decision problems solvable in polynomial time?

It seems obvious that if we define $D_f=\{x|f(x)=1\}$ with $f\in FP_{0,1}$, then $D_f$ is indeed a polynomial-time decidable language. What if we take arbitrary polynomial-time decidable language $L$. Is there always a function $g\in FP_{0,1}$ such that $D_g=L$?

I'm struggling with something that seems to me as a contradiction, and I suspect it arises from some subtle difference between function and decision problems which I overlook.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Yes, if you take a polynomial-time decidable language, that language is always of the form $D_f$ for some polynomial-time computable $\{0,1\}$ valued function - because the definition of polynomial-time decidability is that the characteristic function of the language is polynomial-time computable.

The main distinction between function and decision problems in computational complexity comes from functions that are not $\{0,1\}$ valued. A number-theoretic function $f$ is computable (with no time constraints) if and only if its graph $\{ \langle x,y\rangle : f(x) = y\}$ is computable. But the graph might be polynomial-time computable even though $f$ is not.

For example, this happens when we take $f(x) = 2^x$. The problem is that when we want to decide whether a pair $\langle x,y\rangle$ is in the graph, we can work in time polynomial in $|\langle x,y\rangle|$, which is larger than both $\log(x)$ and $\log(y)$, but to try to compute $f(x)$ in polynomial time we have to bound ourselves to a time limit that is polynomial in $\log(x)$ alone. Now computing $y = 2^x$ in the naive way requires $x$ multiplications of numbers less than $y$, and $\log(y) = \log(2^x) = x$, and multiplication of two numbers less than $y$ requires time that is polynomial in $\log(y)$. So if we are allowed to take a polynomial amount of time relative to $\log(y)$ then we can verify whether $y = 2^x$, thus deciding the graph of $f(x) = 2^x$ in polynomial-time. But we cannot compute $f(x)$ from $x$ alone in polynomial time.

share|improve this answer
    
Thank you. It seems the contradiction I mentioned remains, I might post a question about it later (perhaps on MO). –  rank Sep 21 '12 at 5:02
    
@rank: could you explain what contradiction you see? –  Carl Mummert Sep 21 '12 at 11:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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