Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
@rank: could you explain what contradiction you see? – Carl Mummert Sep 21 '12 at 11:19

Your Answer


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