Two approaches have been devised to study and understand the approximability (or lack thereof) of NP optimization problems: the computational and the syntactic. The computational approach considers the classes APX and PTAS of problems approximable within some (or any, respectively) constant factor, and has led to a lot of fruitful algorithmic development. The syntactic approach considers problem classes based on logical definability, most notably MaxSNP and MaxNP (with bounded and unbounded disjunctions, respectively, in the logical characterization), gives structural information about these classes, and allows natural complete problems at least for MaxSNP. Naturally, there has been much interest in reconciling these two approaches, and this was finally achieved in Khanna et al. [1], which showed that the purely syntactic class MaxSNP is the core of the computational class APX in the following sense: the closure of MaxSNP under PTAS-reductions (or under E-reductions) coincides with APX (or with polynomially bounded APX, or APX-PB, respectively). This result has the important corollary that Max3SAT is complete for MaxNP (under L reductions). The proofs of Khanna et al. [1] rely heavily on the complicated PCP machinery of Arora et al. [2].

This paper uses PTAS reductions to give a significantly simpler proof (in particular, without using PCP) of the following: “Max 3SAT is MaxNP hard under PTAS reductions.” The new reduction provides structural insights into the relationship between MaxSNP and MaxNP; it cleverly exploits the intuition that the long disjunctions of MaxNP are easy to satisfy (probabilistically) and thus cannot make the problem harder. A judicious combination of the probabilistic method for satisfying long clauses and the standard method (local replacement) for satisfying short clauses gives an approximation-preserving reduction, embodied in the “disjunction shrinking theorem”; the rest follows easily.

The disjunction shrinking technique is shown to be provably better than local replacement, for which inherent limitations had been exhibited in Trevisan et al. [3]. Curbing the optimism of this approach, the paper also presents reasons why the same approach will not work for APX-hardness: a weak PCP theorem is necessarily contained in any proof of the APX-hardness of Max3SAT.

Syntactic classes with input restrictions corresponding to planarity were proposed in Khanna and Motwani [4] as a possible core for the computational class PTAS. While no exact characterizations have yet been obtained, the importance of the planarity restriction is evident. In this paper, the disjunction-shrinking technique is also used, along with techniques from Khanna and Motwani [4], to present linear-time approximation schemes for planar restrictions of some important problems.