1
$\begingroup$

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):

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?

$\endgroup$
  • $\begingroup$ With "ML" you are referring to ML right? $\endgroup$ – uli Apr 22 at 12:49
  • $\begingroup$ Thanks @uli. Sorry I wasn't clear. I was referring to machine learning. I updated the post accordingly. $\endgroup$ – Amelio Vazquez-Reina Apr 22 at 12:55
  • $\begingroup$ Ah, all the young folks messing with the established abbreviations .... $\endgroup$ – uli Apr 22 at 13:01
  • $\begingroup$ You can add an objective function to sorting so that the sorted sequence gets min cost/max points and then interpret the problem of sorting a sequence as the optimization problem of finding the sequence with min cost/max points (the sorted one). That just makes things more complicated. My guess for sorting is that the objective function should not be too hard to find. I guess it would fit on a single sheet of paper. But for anything more involved the objective function is most likely not "simple", "linear", has a closed form and fits on one sheet of paper. $\endgroup$ – uli Apr 22 at 15:12
  • $\begingroup$ And constructing the objective functions in general or perhaps even automatically is probably a whole other matter. Take for example linear programming. If you are a carpenter or a tailor and want to solve the cutting-stock-problem via linear programming. You have to come up with the concrete objective function for the linear programm for your scenario to limit the waste of material. This is an art in itself. $\endgroup$ – uli Apr 22 at 15:19
1
$\begingroup$

Search problems are in NP if you can verify a solution in polynomial time.

Counting problems are ♯P if you're counting the number of solutions to an NP search problem.

Enumeration problems are not particularly special.

See https://en.wikipedia.org/wiki/Computational_problem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but couldn't one reframe these problems as optimization problems using a loss function? e.g. $\text{argmin}_x f(x)$, where f is a measure of error defined against the result of the desired problem. In other words, couldn't one argue that (many?) non-optimization problems are "easily" reducible to optimization problems? Or is that not always feasible? $\endgroup$ – Amelio Vazquez-Reina Apr 21 at 12:01
  • $\begingroup$ @AmelioVazquez-Reina, yes for search problems, no for counting problems. Yes many problems are reducible to optimization problems, which is not the same as saying they are an optimization problem. $\endgroup$ – D.W. Apr 21 at 16:16
  • $\begingroup$ Thanks. Why yes for search but not for counting problems? $\endgroup$ – Amelio Vazquez-Reina Apr 21 at 17:55
  • $\begingroup$ @AmelioVazquez-Reina, I don't know how to give a "why". I don't see how to usefully express a counting problem in that form. $\endgroup$ – D.W. Apr 21 at 18:59

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.