The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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