Periodically specified satisfiability problems with applications: An alternative to domino problems

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 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 axe 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, we show that a number of basic NP-hard problems become EXPSPACE hard when inputs axe represented using 1-dimensional infinite periodic wide specifications. This answers a long standing open question posed by Orlin