What's the deal with Deno? We talk with a major contributor to find out. Listen now.

Hardness of approximation, aka inapproximability.

This tag is for questions related to hardness of approximation (also called inapproximability) of optimization problems.

  • Please consider adding also .
  • Questions specifically related to probabilistically checkable proofs are better tagged as .
  • Questions about approximation algorithms rather than hardness should be tagged as .
  • Questions about NP-hardness of solving optimization problems exactly rather than approximately should be tagged as .