1
$\begingroup$

I just read this definition for the longest path problem:

LONGEST PATH
Input: A graph $G=(V,E)$, an integer $k$.
Question: Is there a path with at least $k$ vertices in $G$

This seems a decision problem and a certificate can be verified easily. But, what is the usage of such a problem? Isn't the main concern finding the longest path in the graph? I guess that would be an optimization problem, and verifying a given certificate can't be done in polynomial time, so that is not $NP$. right?

If yes, then what is the usage of the decision problem (which is $NP$) and what is its relation to the main problem?

My question is different from "NP-complete" optimization problems because I also asked about the relationship between a decision problem and a relevant optimization problem, and how a decision problem may help us in solving the optimization problem, and basically what is their usage in such cases.

$\endgroup$
1
$\begingroup$

In complexity theory, we tend to focus on decision problems. They're conceptually simpler and the corresponding function and optimization problems can be reduced to them with only a polynomial loss of efficiency. From a theoretical point of view, polynomial factors are considered "efficient".

Let's take your example of Longest Path. We know that the longest path has length between 1 and $n$ (where $n$ is the number of vertices), so we can find the actual length of the longest path by doing binary search using a series of queries of the form "Is there a path of length at least $n/2$?", "... $3n/4$?", ... That tells us that the longest path has some length $\ell$. Now, we can loop through the edges one by one. Delete the $i$th edge and ask, "Is there still a path of length at least $\ell$?" If there is, go on to the next edge; if there isn't, undelete edge $i$ and go on to the next one. When this algorithm terminates, we'll be left with a graph that is exactly a path of length $\ell$. We used $\Theta(\log n$) calls to Longest Path to find the length of the longest path, and $O(n^2)$ calls to find the actual path.

The decision problem isn't necessarily "useful" per se: as you observe, the function problem ("Give me a solution", rather than "Is there a solution?") is the one we usually want to solve, practically speaking.

$\endgroup$
  • $\begingroup$ Thanks. I am just not sure if your solution is applicable to all corresponding decision and opt problems. It seems you suppose a lower and upper bound for the optimal solution. Is it the case with all such problems? $\endgroup$ – Ahmad Nov 9 '18 at 17:16
  • 1
    $\begingroup$ @Ahmad I can't imagine a computable problem where there isn't a computable upper bound. But if you can't think of one, then do the less efficient that just counts up from zero. $\endgroup$ – David Richerby Nov 9 '18 at 17:33
  • $\begingroup$ Right! I checked the related answers: cs.stackexchange.com/a/989/21789 and cs.stackexchange.com/a/476/21789. Based on your argument, an NP decision problem implies that its corresponding optimization problem is NP or ONP (whatever you like to name). I couldn't read the other answers completely, but I feel I didn't find your arguments there. $\endgroup$ – Ahmad Nov 9 '18 at 18:46
  • $\begingroup$ "NP" only applies by definition only to decision problems where every instance of a problem has either "yes" or "no" as an answer. Something similar for optimisation problems would be hard to define. Even if an oracle gives you the optimal answer, the question whether that answer is actually optimal is in co-NP. $\endgroup$ – gnasher729 Nov 10 '18 at 18:32

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.