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

<p>See  David Defossez, <a href="http://dl.acm.org/citation.cfm?id=1598868">Complexity of clique-coloring odd-hole-free graphs</a>. 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, <a href="http://arxiv.org/abs/1312.2086">Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3</a> (the problem is still $\Sigma_2^p$-complete for weakly chordal graphs, and for perfect graphs having cliques of size at least 3).</p>

CC BY-SA 3.0
2014-07-01T06:33:39.557Z
2014-07-01T06:33:39.557Z
Marzio De Biasi
<p>Deciding the existence of an "evolutionarily stable strategy" in a normal-form game. See <a href="http://www.cs.duke.edu/~conitzer/ess.pdf">http://www.cs.duke.edu/~conitzer/ess.pdf</a> .</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-30T21:22:17.080Z
2014-06-30T21:22:17.080Z
usul
<p>Marcus Schaefer and Chris Umans have <a href="http://ovid.cs.depaul.edu/documents/phcom.pdf">a nice Garey-and-Johnson-esque survey</a> of complete problems in the polynomial hierarchy.</p>

CC BY-SA 3.0
2014-07-01T00:45:02.270Z
2014-07-01T00:45:02.270Z
Huck Bennett
<p>I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aS">Complexity Zoo</a>, namely:</p>

<ul>
<li>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?</li>
<li>Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F?</li>
</ul>

<p>Another basic $\Sigma_2^p$ complete problem:</p>

<ul>
<li>$\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?</li>
</ul>

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

CC BY-SA 3.0
2014-06-30T15:51:33.630Z
Take a look at this compendium: http://ovid.cs.depaul.edu/documents/phcom.pdf
Huck Bennett
CC BY-SA 3.0
2014-06-30T15:53:54.230Z
This looks extremely useful. Thanks a lot!
gdiazc
CC BY-SA 3.0
2014-06-30T16:02:37.700Z
@HuckBennett: good survey! Why don't you turn it into an answer?
Marzio De Biasi
<complexity-classes><polynomial-hierarchy>
Examples of $\Sigma_2^p$ complete problems?
gdiazc
# Examples of $\Sigma_2^p$ complete problems?

(Asked by: username_0 on 2014-06-30)

I need a list of $\Sigma\_2^p$ complete languages. There are two such problems listed in the [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aS), 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).

**Tags:** complexity-classes, polynomial-hierarchy

> **Comments:**
> **username_1**: Take a look at this compendium: http://ovid.cs.depaul.edu/documents/phcom.pdf  
> **username_0**: This looks extremely useful. Thanks a lot!  
> **username_2**: @HuckBennett: good survey! Why don't you turn it into an answer?  

---

## 3 answers

### Answer by username_1 on 2014-07-01. Score: 20 | Accepted answer

Marcus Schaefer and Chris Umans have [a nice Garey-and-Johnson-esque survey](http://ovid.cs.depaul.edu/documents/phcom.pdf) of complete problems in the polynomial hierarchy.


---

### Answer by username_2 on 2014-07-01. Score: 10

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](http://dl.acm.org/citation.cfm?id=1598868). 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](http://arxiv.org/abs/1312.2086) (the problem is still $\Sigma\_2^p$-complete for weakly chordal graphs, and for perfect graphs having cliques of size at least 3).


---

### Answer by username_3 on 2014-06-30. Score: 8

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.


---

