MAX3SAT is exponentially hard to approximate if NP has positive dimension

AbstractUnder the hypothesis that NP has positive p-dimension, we prove that any approximation algorithm A for MAX3SAT must satisfy at least one of the following: 1.For some δ>0, A uses at least 2nδ time.2.For all ε>0, A has performance ratio less than 78+ε on an exponentially dense set of satisfiable instances. As a corollary, this solves one of Lutz and Mayordomo's “Twelve problems on resource-bounded measure” (Bull. European Assoc. Theoret. Comput. Sci. 68 (1999) 64–80)