patternMinor
Polynomial time optimization problems belong to which complexity class?
Viewed 0 times
belongpolynomialtimeoptimizationwhichproblemsclasscomplexity
Problem
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?
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?
Solution
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)
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)
Context
StackExchange Computer Science Q#139801, answer score: 5
Revisions (0)
No revisions yet.