Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V


The Measure Hypothesis and Efficiency of Polynomial Time Approximation Schemes
Mathias Hauptmann
[Download PostScript] [Download PDF]

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].

Last Change: 11/05/14 at 10:42:15
Universität Bonn -> Institut für Informatik -> Abteilung V