| Определение: |
| [math]\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))[/math]. |
То есть [math]\mathrm{NP}[/math] — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
| Определение: |
| [math]\mathrm{\Sigma_1}=\{L|\exists R(x,y)\in \mathrm{P}, p(n) - poly:x\in L\Leftrightarrow\exists y : |y|\le p(|x|), R(x,y)=1\}[/math]. |
Нестрого говоря, [math]\mathrm{\Sigma_1}[/math] — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор [math]R(x,y)[/math], а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
| Теорема: |
[math]\mathrm{\Sigma_1}=\mathrm{NP}[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
- [math]\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):[/math]
[math]y\leftarrow?\{0,1\}^{\le p(|x|)}[/math]
[math]return[/math] [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]\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] часто называют также "определением NP на языке сертификатов".
Свойства
| Теорема: |
Пусть [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):[/math]
[math]return[/math] [math]p(x)[/math] [math]\&\&[/math] [math]q(x)[/math]
2. Построим программу [math]r[/math], разрешающую [math]L_1\cup L_2[/math]:
[math]r(x):[/math]
[math]return[/math] [math]p(x)[/math] [math]||[/math] [math]q(x)[/math]
3. Построим программу [math]r[/math], разрешающую [math]L_1L_2[/math]:
[math]r(x):[/math]
[math]n\leftarrow|x|[/math]
[math]mid\leftarrow?\{1..n\}[/math]
[math]return[/math] [math]p(x[1..mid])[/math] [math]\&\&[/math] [math]q(x[mid+1..n])[/math]
4. Построим программу [math]r[/math], разрешающую [math]L_1^*[/math]:
[math]r(x):[/math]
[math]n\leftarrow|x|[/math]
[math]prev\leftarrow 1[/math]
[math]do[/math]
[math]cur\leftarrow?\{prev..n\}[/math]
[math]if[/math] [math](!p(x[prev..cur]))[/math]
[math]return[/math] [math]false[/math]
[math]prev\leftarrow cur+1[/math]
[math]while[/math] [math](cur[/math] [math]!=[/math] [math]n)[/math]
[math]return[/math] [math]true[/math]
|
| [math]\triangleleft[/math] |
Примеры NP-языков
- Язык раскрасок графа в [math]k[/math] цветов;
- Язык гамильтоновых графов;
- Задача о клике;
- Тетрис
Все эти языки также являются [math]\mathrm{NP}[/math]-полными. О существовании не полного [math]\mathrm{NP}[/math] языка.
Связь P и NP
Очевидно, что [math]\mathrm{P} \subseteq \mathrm{NP}[/math], так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти редкий [math]\mathrm{NP}[/math]-полный язык; было доказано, что доказательство должно быть нерелятивизующимся; различные попытки найти полиномиальные решения для задач из [math]\mathrm{NPC}[/math]:
