Примеры полных проблем?

Мне нужен список полных языков . Есть две такие проблемы, перечисленные в зоопарке сложности , а именно:$\Sigma_2^p$

• Минимальный эквивалент DNF. Учитывая формулу DNF F и целое число k, существует ли формула DNF, эквивалентная F с k или меньшим числом вхождений литералов?
• Кратчайший имплицит. Учитывая формулу F и целое число k, есть ли конъюнкция k или меньше литералов, что подразумевает F?

Еще одна основная :$\Sigma_2^p$

• $\Sigma_i \text{SAT}$ . При заданной количественной булевой формуле вида , допустимо ли ?$\varphi$$\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$$\varphi$

Тем не менее, я надеюсь, что ищу проблему, которая использует графики (например, проблема, связанная с кликой).

Маркус Шефер и Крис Уманс провели хороший обзор Гари-и-Джонсона-эска полных задач в полиномиальной иерархии.

Сравнительно недавним результатом, не включенным в статью Шефера и Уманса, является 2-КЛИКОВЫЙ ЦВЕТ ОТЛИЧНЫХ ГРАФОВ .

$\Sigma_2^p$

Решение о существовании «эволюционно устойчивой стратегии» в игре нормальной формы. См. Http://www.cs.duke.edu/~conitzer/ess.pdf .

Установка симметричная игра для двух игроков. Эволюционно устойчивая стратегия - это (рандомизированная) стратегия, которая представляет собой (а) симметричное равновесие Нэша и (б) нет хороших «симметричных отклонений»: в этом равновесии, если один игрок может отклониться от какой-либо стратегии и поддерживать равную полезность, тогда другой игрок поступил бы строго хуже, чтобы затем также отклониться от этой стратегии.