The complexity of approximation PSPACE-complete problems for hierarchical specifications

We extend the concept of polynomial time approximation algorithms to apply to problems for hier-archically specied graphs, many of which are PSPACE-complete. Assuming P 6 = PSPACE, the exis-tence or nonexistence of such ecient approximation algorithms is characterized, for several standard graph theoretic and combinatorial problems. We present polynomial time approximation algorithms for several standard PSPACE-hard problems considered in the literature. In contrast, we show that unless P = PSPACE, there is no polynomial time -approximation for any > 0, for several other problems, when the instances are specied hierarchically. We present polynomial time approximation algorithms for the following problems when the graphs are specied hierarchically: minimum vertex cover, maximum 3SAT, weighted max cut, minimum maximal matching, and bounded degree maximum independent set. In contrast, we show that unless P = PSPACE, there is no polynomial time -approximation for any > 0, for the following problems when the instances are specied hierarchically: the number of true gates in a monotone acyclic circuit when all input values are specied and the optimal value of the objective function of a linear program. It is also shown that unless P = PSPACE, a performance guarantee of less than 2 cannot be obtained in polynomial time for the following problems when the instances are specied hierarchically: high degree subgraph, k-vertex connected subgraph and k-edge connected subgraph