**Problem Detail:**

I know that the quantified Boolean formula problem for a formula $$ \psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi $$ where $\phi$ contains no quantifiers and only the variables $x_1, \ldots, x_n, y_1, \ldots, y_n$ is an example of a $\Pi_2^P$-complete problem. However, I wonder whether there are any natural problems known to be $\Pi_2^P$-complete, just as *Circuit Minimization* is a natural $\Sigma_2^P$-complete problem (see Polynomial hierarchy for details)?

###### Asked By : vauge

#### Answered By : Pål GD

There are very many natural complete problems for $\Pi_2^p$, and there is a survey [1] on completeness for levels of the polynomial hierarchy, containing many such problems. The paper *On the complexity of min-max optimization problems and their approximation* [2] contains a nice overview of "min-max problems" with several proofs of completeness. The latter paper is opened with the following sentence:

The computational complexity of optimization problems of the min-max form is naturally characterized by $\Pi_2^p$, the second level of the polynomial-time hierarchy.

**Some problems:** Here are some examples, all of which are $\Pi_2^p$-complete, listed in the aforementioned survey [1].

- $\forall \exists \text{3SAT}$: Given 3-SAT formula $\phi(x,y)$, is it true that for all $x$ there exists a $y$ such that $\phi(x,y)$ is satisfiable?
- NOT-ALL-EQUAL-$\forall\exists\text{3SAT}$
- MINMAX SAT, MINMAX CIRCUIT, MINMAX CLIQUE
- LIST CHROMATIC NUMBER
- GRAPH SATISFIABILITY
- DYNAMIC HAMILTONIAN CIRCUIT, LONGEST DIRECTED CIRCUIT
- SUCCINCT TOURNAMENT REACHABILITY
- CONSTRAINTS OVER PARTIALLY SPECIFIED FUNCTIONS
- ARGUMENT COHERENCE
- 3-COLORING EXTENSION, 2-COLORING EXTENSION
- (STRONG) ARROWING, GENERALIZED RAMSEY NUMBER
- etc., etc.

**References:**

[1] Schaefer, Marcus, and Christopher Umans. "Completeness in the polynomial-time hierarchy: A compendium." SIGACT news 33.3 (2002): 32-49. (PDF)

[2] Ko, Ker-I., and Chih-Long Lin. "On the complexity of min-max optimization problems and their approximation." Minimax and Applications. Springer US, 1995. 219-239. (PDF)

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41531

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback