1
$\begingroup$

Every function problem has a corresponding decision problem, which is simply the graph of the function problem, according to

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

which reads that the time complexity of a function problem and decision problem underlying decision problem "...may not be considered equivalent in some typical models of computation". This seems to be the case with the Greatest Common Divisor decision problem, according to

https://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity

So I'd like to use this as an example. I am having a difficult time understanding why the complexity of the GCD function problem is different than its corresponding decision. If the Decision Problem is simply the graph of the Function problem, which is solvable in under quadratic time, how could the decision problem be solvable only in polynomial time?

$\endgroup$
1
$\begingroup$

The Wikipedia article is confusing.

There are two things going on here.

Here's first thing: the complexity class P is defined to be a class of decision problems. Thus, by definition, no function problem is in P. So it's correct that the decision problem for gcd is in P, but the function problem for gcd is not. Of course, this is pretty trivial. So the first thing is not very interesting -- but it does explain why the Wikipedia article makes that odd comment about the decision problem for gcd being in P.

The second thing is more interesting: is there a difference in the running time between the decision problem and function problem? Sometimes there is. For instance, consider factoring. A function problem is: given a number $t$, factor $t$ into a product of primes. A decision problem is: given a number $t$ and primes $p_1,\dots,p_k$, check whether $t = p_1 \times \dots \times p_k$. There is no known polynomial-time algorithm for the function problem, but there is an easy polynomial-time algorithm for the decision problem. So, it's apparently easier to check whether the answer is correct than to find the answer. Indeed, for any NP-complete problem, we believe it is easier to check the answer than to compute it, so the function problem appears to be harder than one plausible formulation of the decision problem. (For that reason, when we turn function problems into decision problems, we usually do it in a different way than the one you mention.)

What about for gcd? The function problem is: given $x,y$, compute $\gcd(x,y)$. The fastest algorithm known for this takes $O(T(n) \log n)$ time, where $n$ is the number of bits of $x,y$ and $T(n)$ is the time to multiply two $n$-bit numbers. It is an open question whether this can be done faster than that, or exactly how fast this is. A plausible decision problem is: given $x,y,d$, check whether $\gcd(x,y)=d$. Here it is not known what the fastest possible running time is. You can check whether $d$ divides $x$ and $y$ in $O(T(n))$ time, so you can check whether $d | \gcd(x,y)$ in $O(T(n))$ time -- faster than we know how to compute the gcd in the first place. But I don't know of any algorithm to turn this into a way to check whether $d = \gcd(x,y)$ asymptotically faster than computing the gcd from scratch in the first place. So we just don't know in this case whether the decision problem can be solved faster than the function problem.

$\endgroup$
  • $\begingroup$ does the open question (what running times GCD's are in ) have to do with the modulo operations used in the GCD, the fact that their time-cost is not consistent as n increases? $\endgroup$ – Jeff Jan 29 '18 at 18:54
  • $\begingroup$ @Jeff, I don't know how to answer that, exactly. It has to do with the fact that we know of a fairly clever algorithm... but how do we know whether that is the best algorithm? Maybe there is some even-cleverer algorithm that we just haven't thought of yet. $\endgroup$ – D.W. Jan 29 '18 at 18:58
  • $\begingroup$ hmm...but isn't that like anything. Multiplication is in quadratic time, but maybe there's a faster algorithm? I am wondering why we can't simply say it is "at least" in some class? $\endgroup$ – Jeff Jan 29 '18 at 19:04
  • $\begingroup$ @Jeff, I confess I'm not sure I understand what you are asking. The best I can suggest is to do some research on why proving lower bounds is hard to get a little background on that topic, then ask a new question. $\endgroup$ – D.W. Jan 29 '18 at 20:47
  • $\begingroup$ @ D.W., now that you mention "lower bounds" I understand. I misread your sentence: "It is an open question ...exactly how fast this is." For some reason I thought you meant it's an open question what the upper bound is, but that didn't make sense as you already stated its fastest known algorithm's running time. Thanks...I'm good now. $\endgroup$ – Jeff Jan 29 '18 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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