Polynomial time optimization problems belong to which complexity class? I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like &quot;Does there exist an $(s,t)$ path of length $k$ in the graph $G$?&quot; 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: &quot;Find a shortest $(s,t)$ path in the graph $G$&quot;.
Since this is not a decision problem, is it wrong to say that &quot;shortest path problem is in $\mathsf{P}$&quot;? If so, in which complexity class does it belong to?
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 &quot;Finding the shortest $(s,t)$ path in the graph $G$, is a $P$ problem&quot; would actually mean: &quot;Finding the shortest $(s,t)$ path in the graph $G$, is an $FP$ problem&quot; (since the context is clear)