Cheap and Secure Web Hosting Provider : See Now

[Solved]: Are there any natural $\Pi_2^P$-complete problems?

, , No Comments
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

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback