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

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

3 Answers 3

Reset to default
18
$\begingroup$

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

Improve this answer
$\endgroup$
9
$\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).

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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