HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Polynomial time optimization problems belong to which complexity class?

Submitted by: @import:stackexchange-cs··
0
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?

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)

Context

StackExchange Computer Science Q#139801, answer score: 5

Revisions (0)

No revisions yet.