The complexity of approximating PSPACE-Complete problems for hierarchical specifications
<|reference_start|>The complexity of approximating PSPACE-Complete problems for hierarchical specifications: We extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. Assuming P != PSPACE, the existence or nonexistence of such efficient 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 epsilon-approximation for any epsilon>0, for several other problems, when the instances are specified hierarchically. We present polynomial time approximation algorithms for the following problems when the graphs are specified hierarchically: {minimum vertex cover}, {maximum 3SAT}, {weighted max cut}, {minimum maximal matching}, {bounded degree maximum independent set}   In contrast, we show that unless P = PSPACE, there is no polynomial time epsilon-approximation for any epsilon>0, for the following problems when the instances are specified hierarchically: {the number of true gates in a monotone acyclic circuit when all input values are specified} 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 specified hierarchically: {high degree subgraph}, {k-vertex connected subgraph}, and {k-edge connected subgraph}<|reference_end|>
@article{marathe1994the,
    title={The complexity of approximating PSPACE-Complete problems for
  hierarchical specifications},
    author={Madhav V. Marathe, Harry B. Hunt III, S. S. Ravi},
    journal={arXiv preprint arXiv:math/9409225},
    year={1994},
    number={LACES 68Q-94-21},
    archivePrefix={arXiv},
    eprint={math/9409225},
    primaryClass={math.CO cs.CC}
}