Есть ли естественные -полные проблемы?

Я знаю, что проблема количественной булевой формулы для формулы где содержит квантификаторов и только переменные является примером -полной проблемы. Однако мне интересно, существуют ли какие-либо естественные проблемы, известные как -полные, так же, как минимизация контуров является естественной -полной проблемой (подробнее см. Полиномиальная иерархия )?ϕ x 1 , … , x n , y 1 , … , y n Π P 2 Π P 2 Σ P

$$\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi$$ $\phi$$x_1, \ldots, x_n, y_1, \ldots, y_n$$\Pi_2^P$$\Pi_2^P$$\Sigma_2^P$

Для существует очень много естественных полных задач , и существует обзор [1] по полноте для уровней полиномиальной иерархии, содержащий много таких задач. В статье « О сложности задач оптимизации min-max и их аппроксимации» [2] содержится хороший обзор «задач min-max» с несколькими доказательствами полноты. Последний документ открывается следующим предложением:$\Pi_2^p$

Вычислительная сложность задач оптимизации в форме min-max естественным образом характеризуется , вторым уровнем иерархии полиномиального времени.$\Pi_2^p$

Некоторые проблемы: Вот несколько примеров, все из которых -complete, перечислены в вышеупомянутом обзоре [1].$\Pi_2^p$

• $\forall \exists \text{3SAT}$ : заданная формула 3-SAT$\phi(x,y)$$x$$y$$\phi(x,y)$
• $\forall\exists\text{3SAT}$
• MINMAX SAT, MINMAX CIRCUIT, MINMAX CLIQUE
• СПИСОК ХРОМАТИЧЕСКОГО НОМЕРА
• ГРАФ СООТВЕТСТВИЕ
• ДИНАМИЧНАЯ ГАМИЛЬТОНОВАЯ ЦЕПЬ, ДОПОЛНИТЕЛЬНАЯ НАПРАВЛЕННАЯ ЦЕПЬ
• ДОСТУПНАЯ ДОСТУПНОСТЬ ТУРНИРА
• ОГРАНИЧИВАЕТ ЧАСТИЧНО УКАЗАННЫЕ ФУНКЦИИ
• ARGUMENT COHERENCE
• 3-ЦВЕТНОЕ РАСШИРЕНИЕ, 2-ЦВЕТНОЕ РАСШИРЕНИЕ
• (СИЛЬНО) СТРЕЛКА, ОБОБЩЕННЫЙ НОМЕР РАМСЕЯ
• и т. д.

Ссылки:

[1] Шефер, Маркус и Кристофер Уманс. «Полнота в иерархии полиномиального времени: сборник». SIGACT news 33.3 (2002): 32-49. ( PDF )

[2] Ko, Ker-I. И Chih-Long Lin. «О сложности задач оптимизации min-max и их приближении». Минимакс и приложения. Springer US, 1995. 219-239. ( PDF )