Generalized CNF satisfiability problems and non-efficient approximability

摘要

We use variants of the generalized CNF satisfiability problems SAT(S) of T.J. Schhaefer (1978) to characterize the efficient approximability of a number of basic NP and PSPACE-hard optimization problems in the literature. In contrast with the recent results, none of our proofs make use of interactive proof systems or of probabilistically checkable debate systems. In particular assuming P/spl ne/NP- or P/spl ne/PSPACE, we show that a number of the optimization problems shown not to be efficiently approximable can be shown not to be efficiently approximable by direct reductions, often of variants of the problems MAX NSF and ambiguous 3SAT. Moreover, often we show this, not only for arbitrary problem instances but also for planar problem instances and for f(n)-treewidth-bounded instances. Thus analogous to Zuckerman (1993), we show that: "Planar NP-complete, PSPACE-complete, planar PSPACE-complete problems, etc. also have versions that are hard to approximate".