11.02.2008

A polyomial time approximation scheme for an optimization problem X is an algorithm A such that for each instance x of X and each ε > 0, A computes a (1 + ε)-approximate solution to instance x of X in time is O(|x| ^f(1/ε)) for some function f. If the running time of A is instead bounded by g(1/ε) · |x|^O(1) for some function g, A is called an efficient polynomial time approximation scheme. PTAS denotes the class of all NP optimization problems for which a polytime approximation scheme exists, and EPTAS is the class of all such problems for which an efficient polytime approximation scheme exists. It is an open question whether P ≠ NP implies the strictness of the inclusion EPTAS ⊆ PTAS. Bazgan (1995) and independently Cesati and Trevisan (1997) gave a separation under the stronger assumption FPT ≠ W[P]. In this paper we prove EPTAS ≠ PTAS under some different assumption, namely existence of NP search problems Π_R with a superpolynomial lower bound for the deterministic time complexity. This assumption is weaker than the NP Machine Hypothesis (Hitchcock 2004) and hence is implied by the Measure Hypothesis μ_p(NP) ≠ 0. Furthermore, using a sophisticated combinatorial counting argument we construct a recursive oracle under which our assumption holds but that of Cesati and Trevisan does not hold, implying that using relativizing proof techniques one cannot show that our assumption implies FPT ≠ W[P].