APX-hardness and APX-completeness under L-reductions

Under the explicitly selected L-reduction convention of L-reductions between optimization problems, an optimization problem $\mathrm{\Gamma }$ in the finite-instance model is APX-hard when every problem $\mathrm{\Pi }$ in the locally defined class APX has an L-reduction to $\mathrm{\Gamma }$. The problem $\mathrm{\Gamma }$ is APX-complete under this convention when it is APX-hard and also belongs to APX.

The class APX here is the one fixed in PTAS, FPTAS and APX: problems in the finite-instance model of Optimization problems and approximation ratios that admit one polynomial-time fixed-factor approximation in their objective direction. Thus APX-hardness quantifies over every such source problem, with the reduction maps and constants of L-reductions between optimization problems, and APX-completeness adds membership of the target in that class. The reduction notion is part of this definition: this page explicitly chooses L-reductions and does not claim that all of the literature uses the same convention for APX-hardness or APX-completeness.

No concrete target is certified APX-hard or APX-complete here. In particular a PCP constant-gap or no-PTAS result, such as the consequences proved on this page for Max-3SAT and maximum independent set, establishes no APX-hardness or APX-completeness under this definition; those self-contained no-PTAS arguments do not exhibit L-reductions from all APX problems. The composition and transfer properties of this reduction notion are established separately in L-reductions compose and transfer PTAS and APX-hardness.