APXhard

APXhard is a term used in computational complexity theory to describe a certain level of difficulty for optimization problems, specifically in the realm of approximation algorithms. It characterizes problems that are at least as hard to approximate as the hardest problems in a particular class known as APX.

APX is the class of optimization problems for which there exists a polynomial-time algorithm that produces a solution whose objective value is within a constant factor c ≥ 1 of the optimum, for every instance. APX-hard means that every problem in APX can be reduced to the problem in question via approximation-preserving reductions, often called AP-reductions. These reductions map instances and solutions in a way that preserves the quality of approximations up to a constant factor, ensuring that if one could approximate the target problem well, one could also approximate every APX problem well.

When a problem is both in APX and APX-hard, it is called APX-complete. This designation suggests the problem is among the most challenging in APX with respect to approximability. A common implication discussed in the literature is that APX-hard problems are not expected to admit a polynomial-time approximation scheme (PTAS) unless widely believed complexity-theoretic separations fail (for example, unless P = NP). However, the exact existence of a PTAS for a given APX-hard problem is not guaranteed by the classification alone and depends on deeper structural properties.

In practice, APXhard serves as a benchmark for the difficulty of achieving near-optimal solutions within a constant factor, highlighting problems whose approximability is as hard as the hardest problems in APX. See also APX, approximation algorithms, and AP-reductions.