The top accepted answers to the questions below allude to two complexity classes of optimization problems: NPO and PO (in relation to NP and P for decision problems):
- Decision problems vs "real" problems that aren't yes-or-no
- Optimization version of decision problems
- “NP-complete” optimization problems
The way these questions and answers are written, I get the impression that many problems such as counting, enumeration, or searching problems could be framed as general optimization problems even if their formulation does not have an explicit objective function (i.e. mathematical programming problems). Is that correct?
Take decision problems for example, one often casts decisions in machine learning (ML) as those that minimize regret, or e.g. an expected error in the evaluation against a loss function (e.g. 0/1 for decision problems).
These types of decisions or search as-optimization formulations for a wide variety of problems are fairly ubiquitous in ML.
Take some other common examples:
- Find the $n$th Fibonacci term
- Find the GCD of a set of numbers
- Enumerate the subsets for which 3SUM answers "Yes"
- Count all hamiltonian cycles in a graph
- etc.
Couldn't one easily reframe many of them as optimization problems using a loss function as well? e.g. $\text{argmin}_x f(x)$, where $f$ is a measure of error defined on the solution space of the desired problem? Or is that reduction, despite its prevalence in e.g. ML, not always "easy", feasible or useful?
More generally, how does the family of complexity classes (and their associated types of reductions and definitions) for search, enumeration and counting relate to the family of their "reduction-equivalent" optimization problems?
