3
$\begingroup$

I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can first find the shortest path from $s$ to $t$ in polynomial time and check if it is smaller than $k$ or not.

Now, consider the optimization version of this problem that we popularly call the shortest path problem: "Find a shortest $(s,t)$ path in the graph $G$". Since this is not a decision problem, is it wrong to say that "shortest path problem is in $\mathsf{P}$"? If so, in which complexity class does it belong to?

$\endgroup$

1 Answer 1

5
$\begingroup$

Take a look at the FP complexity class.

Technically speaking, it is wrong. However, usually people don't make a huge difference between the two. Its usually clear from the context whether the problem is a decision or a search problem, hence its clear whether it should be in $P$ or $FP$.

So, writing that "Finding the shortest $(s,t)$ path in the graph $G$, is a $P$ problem" would actually mean: "Finding the shortest $(s,t)$ path in the graph $G$, is an $FP$ problem" (since the context is clear)

$\endgroup$

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.