Examples of $\Sigma_2^p$ complete problems?

Question

I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the Complexity Zoo, namely:

Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?
Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F?

Another basic $\Sigma_2^p$ complete problem:

$\Sigma_i \text{SAT}$. Given a quantified boolean formula $\varphi$ of the form $\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$, is $\varphi$ valid?

However, I am hopefully looking for a problem which makes use of graphs (e.g. a clique related problem).

Take a look at this compendium: http://ovid.cs.depaul.edu/documents/phcom.pdf — Huck Bennett, Jun 30 '14 at 15:51
@HuckBennett: good survey! Why don't you turn it into an answer? — Marzio De Biasi, Jun 30 '14 at 16:02

score 18 · Accepted Answer · answered Jul 01 '14 at 00:45

18

Marcus Schaefer and Chris Umans have a nice Garey-and-Johnson-esque survey of complete problems in the polynomial hierarchy.

answered Jul 01 '14 at 00:45

Huck Bennett

4,868
2
33
46

score 9 · Answer 2 · answered Jul 01 '14 at 06:33

A rather recent result not included in the Schaefer and Umans paper is 2-CLIQUE COLOURING OF PERFECT GRAPHS.

See David Defossez, Complexity of clique-coloring odd-hole-free graphs. J. Graph Theory 62, 2 (October 2009), 139-156, and some recent improvements (2013): Hélio B. Macêdo Filho, Raphael C. S. Machado, Celina M. H. de Figueiredo, Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 (the problem is still $\Sigma_2^p$-complete for weakly chordal graphs, and for perfect graphs having cliques of size at least 3).

score 7 · Answer 3 · answered Jun 30 '14 at 21:22

Deciding the existence of an "evolutionarily stable strategy" in a normal-form game. See http://www.cs.duke.edu/~conitzer/ess.pdf .

The setup is a 2-player symmetric game. An evolutionarily stable strategy is a (randomized) strategy that is (a) a symmetric nash equilibrium, and (b) there are no good "symmetric deviations": in this equilibrium, if one player can deviate to some strategy and maintain equal utility, then the other player would do strictly worse to then also deviate to this strategy.

Examples of $\Sigma_2^p$ complete problems?

3 Answers3