Generalized CNF satisfiability, local reductions and complexity of succinctly specified problems

摘要

We study the complexity and efficient approximability of various decision, counting and optimization problems when instances are specified using (1) the 1-dimensional finite periodic narrow specifications of Wanke, (2) the 2-way infinite 1-dimensional narrow periodic (sometimes called dynamic) specifications of Karp and Orlin et al., and (3) the hierarchical specification language of Lengauer et al. We outline how generalized CNF satisfiability problems and local reductions can be used to obtain both hardness and easiness results for a number of decision, counting, optimization and approximate optimization problems when instances are specified as in (1), (2) or (3). As corollaries we obtain a number of new PSPACE-hardness and (number sign)PSPACE-hardness,9 results and a number of new polynomial time approximation algorithms for natural PSPACE-hard optimization problems. In particular assuming P (ne) PSPACE, we characterize completely the complexities of the generalized CNF satisfiability problems SAT(S) of Schaefer (Sc78), when instances are specified as in (1), (2) or (3).