Theory of periodically specified problems: complexity and approximability
MADHAV V. MARATHE, Harry B. Hunt, Daniel J. Rosenkrantz, Richard Edwin Stearns · 2002
We study the complexity and the efficient approximability of graph and satisfiability problems when specified using various kinds of periodic specifications studied previously. We obtain two general results. First, we characterize the complexities of several basic generalized CNF satisfiability problems SAT(S), when instances are specified using various kinds of 1- and 2-dimensional periodic specifications. We outline how this characterization can be used to prove a number of new hardness results for periodically specified problems for various complexity classes. As one corollary, we show that a number of basic NP-hard problems become EXPSPACE-hard when inputs are represented using 1-dimensional infinite periodic wide specifications, thereby answering an open question. Second, we outline a simple yet a general technique to devise approximation algorithms with provable worst case performance guarantees for a number of combinatorial problems specified periodically. Our efficient approximation algorithms and schemes are based on extensions of the previous ideas. They provide the first nontrivial collection of natural NEXPTIME-hard problems that have an /spl epsiv/-approximation (or PTAS).