# Function problem vs. decision problem

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.

-

## 1 Answer

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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.938015878200531, "perplexity_flag": "head"}