10
$\begingroup$

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)?

$\endgroup$
11
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.