1
$\begingroup$

I have been studying Integer Programming and I find out that some optimization problems are referred to as P or NP-Hard, however, as I started to read about it, it turns out that those classes are just for decision problem. Thus:

  1. What does it mean that an optimization problem ($\max\{f(c)\mid x\in X\}$) is NP or NP-Hard if they are not (necessarily) decision problems?
  2. If an optimization problem ($\max\{f(c)\mid x\in X\}$) is not a decision problem, then, how is its difficulty classified?
$\endgroup$
2
$\begingroup$

When we say that the optimization problem $\max \{ f(x) : x \in X \}$ is NP-hard, what we really mean is that the following decision problem is NP-hard:

Is there an $x \in X$ such that $f(x) \geq y$?

This turns optimization into a decision problem that can be analyzed using the complexity classes you know of.

There are also complexity classes specifically for functions or for optimization problems. Some examples are:

  • FP, the class of functions computable in polynomial time;
  • APX, the class of problems that can be approximated in polynomial time, and the associated classes APX-hard and MaxSNP;
  • PPAD and its friends, classes of problems of the general form "given $x$, find $y$ such that $P(x,y)$", where for each $x$ we are guaranteed that such a $y$ exists.
$\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.