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 cc.complexity-theory.
- Questions specifically related to probabilistically checkable proofs are better tagged as pcp.
- Questions about approximation algorithms rather than hardness should be tagged as approximation-algorithms.
- Questions about NP-hardness of solving optimization problems exactly rather than approximately should be tagged as np-hardness.