Periodically specified satisfiability problems: An alternative to domino problems
MADHAV V. MARATHE, Daniel J. Rosenkrantz, Richard Edwin Stearns · University of North Texas Digital Library (University of North Texas) · 1997
The authors 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. They outline how this characterization can be used to prove a number of new hardness results for the complexity classes DSPACE(n), NSPACE(n), DEXPTIME, NEXPTIME, EXPSPACE etc. The hardness results presented significantly extend the known hardness results for periodically specified problems. Several advantages are outlined of the use of periodically specified satisfiability problems over the use of domino problems in proving both hardness and easiness results. As one corollary, the authors show that a number of basic NP-hard problems become EXPSPACE-hard when inputs are represented using 1-dimensional infinite periodic wide specifications. This answers a long standing open question posed by Orlin. The results can also be used as starting points for proving the hardness of a number of combinatorial problems when instances are specified succinctly using various succinct specifications. These results significantly extend the results of earlier research in this area.