
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2008  Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V  
85286 11.02.2008 
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
English 
Universität Bonn > Institut für Informatik > Abteilung V 