3
$\begingroup$

Consider the class NP of problems whose solutions can be verified in polynomial time. For some problems in NP, there may not be polynomial algorithms that solve them.

However, in practice, it is common to approximate solutions. In practice, this is acceptable as long as the approximate solution converges to the exact solution with the number of steps involved. Is there a complexity class of problems that can be efficiently approximated?

Such an approximation machine would have access to random number generation. What is the relationship of that class, if it is defined and P and NP? Note: I understand that the class I'm referring to may not be well defined - in that case the question is what's the closest thing possible.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ "the approximate solution converges to the exact solution with the number of steps involved" <<< That sounds like a misconception about approximation algorithms. For many kinds of problem, an approximate (meaning: slightly suboptimal) solution cannot be refined into a better approximation with "more steps". $\endgroup$ Commented Apr 1 at 8:10
  • $\begingroup$ Of course if your problem is "find pi", then you can refine any approximate solution with more steps to add more digits, or if your problem is "locate and superpose this small drone picture onto this big satellite picture" then you can refine the alignment with more steps. But if your problem is the Knapsack Problem, then an approximate solution is a solution whose score is "close to the optimal score", but only the score is close to optimal: the approximate solution itself might be very different from any optimal solution. $\endgroup$ Commented Apr 1 at 8:14
  • $\begingroup$ The complexity class APX is "is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant." $\endgroup$ Commented Apr 1 at 21:00

1 Answer 1

Reset to default
6
$\begingroup$

The question is rather vague as to what kind of problems you want to consider and what does it mean to “approximate” them. (P and NP consist of decision problems, i.e., with 0–1 output, and there is no sensible notion of approximation for that.) But FPRAS may be close to what you are looking for; see https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme , where other related classes are defined as well.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.