Difference b/w Functional and Decisional Problem's computational complexity

Question

I am trying to understand the difference b/w functional and decisional problems. The core as I understand is this:

Functional Problems: Given an input $x$ we calculate some function $f(x)=y$ over it.

Decisional Problems: Given inputs we output YES or NO depending on some logic or algorithm.

As far as I have read a functional problem can always be converted into a decisional problem as follows:

For any functional problem $f(x)=y$ where we compute $y$ we instead post this as a decision problem $d(x, y)$. The output is YES, if $f(x)=y$ and no otherwise. Thus, the Turing Machine which internally encodes the function $f(x)$'s logic, takes the potential (input, output) pair and decides if the given input can achieve the given output according to the internally encoded logic of $f(x)$.

Query 1: Let the Turing machine $T_f$ reads input $x$ and outputs the calculated output $f(x)$ on the tape and halts. Let the second Turing machine $T_d$ reads the pair of values $x, f(x)$ decide that the $f(x)$ is achievable from $x$ or not and accordingly outputs YES or NO on tape and halts.

Won't both of these Turing Machines have the same computational complexity? In fact they would have nearly the same running time since in both cases we are calculating the same function $f(x)$: In $t_f$ we output the calculated value and in $T_d$ we compare the calculated value to the second input and output YES/NO? But wiki states otherwise:

https://en.wikipedia.org/wiki/Decision_problem

"Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair $(x,y)$) when the function is not computable in polynomial time (in which case running time is computed as a function of x alone). The function $f(x) = 2^x$ has this property."

What am I missing? Can someone please elaborate.

Answer 1

What you're missing:

First, given $x,y$, there might be an easier way to test whether $f(x)=y$, without having to compute $f$ on input $x$. For instance, when $x$ is an integer, suppose that $f(x)$ outputs the factorization of $x$. This is believed to be hard to compute (there is no known polynomial-time algorithm). But if you give me a candidate factorization, I can very efficiently verify whether it is a correct factorization (it can be done in polynomial time).

Second, as Wikipedia explains even though both Turing machines have the same running time as a function of the length of $x$, they do not have the same running time as a function of the length of the input. The length of $y$ might be much larger than the length of $x$, so the length of the input $(x,y)$ to the second Turing machine might be much larger than the length of the input to the first Turing machine. The computational complexity is measured as a function of the length of the input. So, the same running time (namely, $x$) might be an exponential function of the length of the input to the first Turing machine (namely, $\lg x$), but be a polynomial function of the length of the input to the second Turing machine (namely, $x+\lg x$, in the example given in Wikipedia).