patternModerate
Are there any natural $\Pi_2^P$-complete problems?
Viewed 0 times
areanypi_2problemscompletenaturalthere
Problem
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)?
$$
\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)?
Solution
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].
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)
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)
Context
StackExchange Computer Science Q#41531, answer score: 11
Revisions (0)
No revisions yet.