A message from our CEO about the future of Stack Overflow and Stack Exchange. Read 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 .
history | excerpt history