1
$\begingroup$

An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known.

Symmetrically, is there a standard name for all those optimisation problems for which a polynomial algorithm is known?

$\endgroup$
3
$\begingroup$

An optimization problem is an example of a function problem: i.e., one where the task is to map some input to some output. The class of function problems solvable in polynomial time is FP. See, for example, the Complexity Zoo.

(Note that there is a class OptP but that's not the polynomial-time optimization problems. Perhaps confusingly, it's the optimization analogue of NP: it's the class of functions that can be defined by taking the maximum out the outputs given by accepting paths of a nondeterministic polynomial-time Turing machine.)

$\endgroup$
1
$\begingroup$

The book Complexity and Approximation by Ausiello et al. uses the name PO for the class of optimization problems that can be solved optimally in polynomial time.

$\endgroup$

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.