Определения, связь Σ₁ и NP
| Определение: |
| [math]\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\!\!\operatorname{NTIME}(p(n))[/math]. |
То есть [math]\mathrm{NP}[/math] — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
| Определение: |
| [math]\mathrm{coNP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}[/math]. |
То есть [math]\mathrm{coNP}[/math] — это множество языков, дополнение к которым лежит в [math]\mathrm{NP}[/math].
| Определение: |
| [math]\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in poly : x\in L\Leftrightarrow\exists y : |y|\leqslant p(|x|), R(x,y)=1\}[/math]. |
Нестрого говоря, [math]\mathrm{\Sigma_1}[/math] — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор [math]R(x,y)[/math], а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
| Определение: |
| [math]\mathrm{\Pi_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in poly : x\in L\Leftrightarrow\forall y : |y|\leqslant p(|x|), R(x,y)=1\}[/math]. |
То есть [math]\Pi_1[/math] — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор [math]R(x,y)[/math], а для каждого слова из языка (и только для слова из языка) нельзя предъявить сертификат длины, ограниченной неким полиномом, опровергающий принадлежность слова языку и проверяемый верификатором. Легко видеть, что [math]\Pi_1[/math] — множество языков, дополнения к которым лежат в [math]\Sigma_1[/math].
| Теорема: |
[math]\mathrm{\Sigma_1}=\mathrm{NP}[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]\Rightarrow \quad(\mathrm{\Sigma_1} \subset \mathrm{NP})[/math].
- Пусть [math]L \in \mathrm{\Sigma_1}[/math]. Тогда существуют [math]R(x,y)[/math] и полином [math]p[/math] из определения [math]\mathrm{\Sigma_1}[/math]. Построим недетерминированную программу [math]q(x)[/math], разрешающую [math]L[/math].
[math]q(x)\colon[/math]
[math]y = \{0,1\}^{p(|x|)}[/math]
return [math]R(x,y)[/math]
- Если [math]x\in L[/math], то программа сможет «угадать» подходящий сертификат. Если [math]x\notin L[/math], то подходящего сертификата не существует по определению. Таким образом, [math]q[/math] разрешает [math]L[/math], следовательно [math]L\in \mathrm{NP}[/math].
[math]\Leftarrow \quad(\mathrm{NP} \subset \mathrm{\Sigma_1})[/math].
- Пусть [math]L\in \mathrm{NP}[/math]. Тогда существует недетерминированная программа [math]q(x)[/math], разрешающая этот язык. Построим верификатор [math]R(x,y)[/math]. В качестве сертификата будем использовать последовательность выборов в программе [math]q[/math], приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в [math]q[/math] может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе [math]q[/math], только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если [math]x\in L[/math], то в [math]q[/math] существует последовательность выборов таких, что [math]q(x)=1[/math], следовательно существует и верный сертификат. Если [math]x\notin L[/math], то для любой последовательности выборов [math]q(x)=0[/math], следовательно подходящего сертификата не существует. Таким образом, [math]L \in \mathrm{\Sigma_1}[/math].
|
| [math]\triangleleft[/math] |
Примечание: определение [math]\mathrm{\Sigma_1}[/math] часто называют также «определением [math]\mathrm{NP}[/math] на языке сертификатов», а [math]\Pi_1[/math], соответственно, «определением [math]\mathrm{coNP}[/math] на языке сертификатов».
Свойства
| Теорема: |
Пусть [math]L_1,L_2\in \mathrm{NP}[/math]. Тогда:
- [math]L_1\cap L_2\in \mathrm{NP}[/math].
- [math]L_1\cup L_2\in \mathrm{NP}[/math].
- [math]L_1L_2\in \mathrm{NP}[/math].
- [math]L_1^*\in \mathrm{NP}[/math].
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]p[/math] разрешает [math]L_1[/math], а [math]q[/math] разрешает [math]L_2[/math].
- 1. Построим программу [math]r[/math], разрешающую [math]L_1\cap L_2[/math]:
[math]r(x)\colon[/math]
return [math]p(x)[/math] and [math]q(x)[/math]
- 2. Построим программу [math]r[/math], разрешающую [math]L_1\cup L_2[/math]:
[math]r(x)\colon[/math]
return [math]p(x)[/math] or [math]q(x)[/math]
- 3. Построим программу [math]r[/math], разрешающую [math]L_1L_2[/math]:
[math]r(x)\colon[/math]
[math]n = |x|[/math]
[math]mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}[/math]
return [math]p(x[1 \mathinner{\ldotp\ldotp} mid])[/math] and [math]q(x[mid+1 \mathinner{\ldotp\ldotp} n])[/math]
- 4. Построим программу [math]r[/math], разрешающую [math]L_1^*[/math]:
[math]r(x)\colon[/math]
[math]n = |x|[/math]
[math]prev = 1[/math]
do
[math]cur \gets?\ \{prev \mathinner{\ldotp\ldotp} n\}[/math]
if not [math]p(x[prev \mathinner{\ldotp\ldotp} cur])[/math]
return false
[math]prev = cur + 1[/math]
while [math]cur \ne n[/math]
return true
- Цикл совершит не более [math]n[/math] итераций, т.к. на каждой итерации левая граница диапазона увеличивается как минимум на 1.
|
| [math]\triangleleft[/math] |
Примеры языков из NP
Язык палиндромов
Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит [math]\mathrm P[/math], а следовательно, и [math]\mathrm{NP}[/math].
Язык задачи о раскраске вершин графа в [math]k[/math] цветов
Переформулируем задачу в терминах принадлежности языку: пусть [math] L = \{ \langle G, k \rangle \mid [/math] вершины [math]G[/math] можно раскрасить в [math]k[/math] цветов [math]\}[/math].
Этот язык разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин и рёбер время:
[math]r(\langle G, k \rangle)\colon[/math]
[math]n = |V(G)|[/math]
[math]c \gets?\ \{ 1, \dotsc, k \} ^ n[/math]
for [math]uv[/math] in [math]E(G)[/math]
if [math]c[u][/math] == [math]c[v][/math]
return false
return true
Язык гамильтоновых графов
[math]r(G)\colon[/math]
[math]n = |V(G)|[/math]
[math]p \gets?\ V(G) ^ n[/math]
for [math]v[/math] in [math]V(G)[/math]
if [math]v \notin p[/math]
return false
[math]p[n + 1] = p[1][/math]
for [math]i = 1[/math] to [math]n[/math]
if [math]p[i]p[i + 1] \notin E(G)[/math]
return false
return true
Два последних языка также являются [math]\mathrm{NP}[/math]-полными. По теореме Ладнера, если [math]\mathrm{P \ne NP}[/math], то существует язык из [math]\mathrm{NP}[/math], не являющийся [math]\mathrm{NP}[/math]-полным.
Примеры языков из coNP
Язык графов, не являющихся гамильтоновыми
Этот язык принадлежит [math]\mathrm{coNP}[/math], так как является дополнением к языку гамильтоновых графов, принадлежащему [math]\mathrm{NP}[/math], как показано выше.
TAUT
Язык булевых формул, являющихся тавтологиями. К этому языку тривиально сводится дополнение к [math]\mathrm{SAT}[/math]: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
Связь P и NP
Очевидно, что [math]\mathrm{P} \subseteq \mathrm{NP}[/math], так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти редкий [math]\mathrm{NP}[/math]-полный язык; было доказано, что доказательство должно быть нерелятивизующимся.
Кроме того, были предприняты различные попытки найти полиномиальные решения для задач из [math]\mathrm{NPC}[/math]:
- «решение» 3SAT за полиномиальное время[1]
- задача о коммивояжёре[2].
Некоторые задачи из [math]\mathrm{P}[/math] очень похожи на задачи из [math]\mathrm{NP}[/math], при этом различие между задачами кажется совершенно незначительным:
Примечания
См. также
