# How is the difficulty of any problem (not just decition problems) classified?

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?

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.