On approximation scheme preserving reducibility and its applications

In this paper we introduce a new polynomial-time approximation scheme prese rving reducibility, which we call PTAS-reducibility, that generalizes previ ous definitions. As a first application of this generalization, we prove th e APX-completeness under PTAS-reducibility of a polynomially bounded optimi zation problem, that is, an APX problem whose measure function is bounded b y a polynomial in the length of the instance and such that any APX problem is PTAS-reducible to it. As far as we know, no such problem was known befor e, This result combined with results of Khanna et al. allows us to infer th at several natural optimization problems are APX-complete under PTAS-reduci bility, such as MAX CUT and MAX SAT. Successively, we apply the notion of A PX-completeness under PTAS-reducibility to the study of the relative comple xity of evaluating an r-approximate value and computing an r-approximate so lution for any r. We first show that if P not equal NP boolean AND coNP, th en the former question can be easier than the latter even if the optimizati on problem is NP-hard. We then give strong evidence that if an optimization problem is APX-complete under PTAS-reducibility, then the two questions ar e both hard.