Theoretical Computer Science
complexity-classes polynomial-hierarchy
Updated Thu, 26 May 2022 13:27:16 GMT

Examples of $\Sigma_2^p$ complete problems?

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


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