A Unified Approach for Proving Both Easiness and Hardness Results for Succinct Specifications (Preliminary Version)
Harry B. Hunt, Madha V. Marathe, R. Venkatesh Babu, Daniel J. Rosenkrantz, Richard Edwin Stearns · 1995
We study the complexity and approximability of various basic decision, counting and optimization problems, when problem instances are specified succinctly by the hierarchical specification language of Lengauer et al. [Le86,LW87a,Le88,Le89,LW92] the periodic (sometimes called dynamic) specifications of Karp and Orlin et al. [KMW67,Or82,CM89], and the finite periodic specifications of Wanke [Wa93]. Several different kinds of generalized satisfiability problems are defined, when instances are specified by these types of specifications. Then, we outline how these problems, together with local reductions, can be used to obtain both hardness and easiness results for a number of decision, counting, optimization and approximate optimization problems. As corollaries we obtain a number of new PSPACE-, PSPACE-, NDEXPTIME- and EXPSPACE-hardness results and a number of new polynomial time approximation algorithms for natural PSPACE-hard optimization problems. Our results answer open questions raised in [CF+93,La89,LW92,Or82,Or84]. Classification: Succinct Specifications, Computational Complexity Efficient and Non-Efficient Approximability.