1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Thank you. I understood both parts. Follow up query though: 1. For an input $x$ with running time of $T_f$ given by some function $r_f(|x|)$ can we ALWAYS have a logic/function such that the decision version Turing machine $T_d$ has also the same running time i.e. $r_f(|x|)=r_d(|x|)$. Notice we even in decision variant are using the running time only over $x$? $\endgroup$
    – student0
    Dec 20, 2022 at 10:31
  • $\begingroup$ 2. In this link of problems in $P$ (en.wikipedia.org/wiki/P-complete) the examples are: "Circuit Value Problem (CVP) – Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate." Aren't they supposed to be just YES/NO problems in P. These seem functional version examples. I am confused here? $\endgroup$
    – student0
    Dec 20, 2022 at 10:37
  • $\begingroup$ @student0, If you have a new/follow-up question, I'd suggest asking a new question. This site isn't really designed for interactive back-and-forth / conversation. $\endgroup$
    – D.W.
    Dec 20, 2022 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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