17
$\begingroup$

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

$\endgroup$
3
  • 10
    $\begingroup$ Take a look at this compendium: ovid.cs.depaul.edu/documents/phcom.pdf $\endgroup$ Jun 30 '14 at 15:51
  • $\begingroup$ This looks extremely useful. Thanks a lot! $\endgroup$
    – gdiazc
    Jun 30 '14 at 15:53
  • 5
    $\begingroup$ @HuckBennett: good survey! Why don't you turn it into an answer? $\endgroup$ Jun 30 '14 at 16:02
16
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\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.