Processing...

### The complexity of approximating PSPACE-Complete problems for hierarchical specifications

**1994-09-21**

9409225 | math.CO

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}

**Login to like/save this paper, take notes and configure your recommendations**