Изменения
Новая страница: «{{Определение |definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>. }} То есть <tex>\mathrm{NP}</tex> — это...»
{{Определение
|definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\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\}</tex>.
}}
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
{{Теорема
|statement=
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
|proof=
*<tex>\mathrm{\Sigma_1} \subset \mathrm{NP}</tex>.
Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда сщуествуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
<tex>q(x):</tex>
<tex>y\leftarrow?\{0,1\}^{\le p(|x|)}</tex>
<tex>return</tex> <tex>R(x,y)</tex>
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
Пусть <tex>L\in \mathrm{NP}</tex>. Тогда существует недетерминированная программа <tex>q(x)</tex>, разрешающая этот язык. Построим верификатор <tex>R(x,y)</tex>. В качестве сертификата будем использовать последовательность выборов в программе <tex>q</tex>, приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в <tex>q</tex> может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе <tex>q</tex>, только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если <tex>x\in L</tex>, то в <tex>q</tex> существует последовательность выборов таких, что <tex>q(x)=1</tex>, следовательно существует и верный сертификат. Если <tex>x\notin L</tex>, то для любой последовательности выборов <tex>q(x)=0</tex>, следовательно подходящего сертификата не существует. Таким образом, <tex>L \in \mathrm{\Sigma_1}</tex>.
}}
'''Примечание:'''определение <tex>\mathrm{\Sigma_1}</tex> часто называют также "определением NP на языке сертификатов".
=== Свойства ===
{{Теорема
|statement=
Пусть <tex>L_1,L_2\in \mathrm{NP}</tex>. Тогда:
#<tex>L_1\cap L_2\in \mathrm{NP}</tex>;
#<tex>L_1\cup L_2\in \mathrm{NP}</tex>;
#<tex>L_1L_2\in \mathrm{NP}</tex>;
#<tex>L_1^*\in \mathrm{NP}</tex>.
|proof=
Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
<tex>r(x):</tex>
<tex>return</tex> <tex>p(x)</tex> <tex>\&\&</tex> <tex>q(x)</tex>
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
<tex>r(x):</tex>
<tex>return</tex> <tex>p(x)</tex> <tex>||</tex> <tex>q(x)</tex>
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
<tex>r(x):</tex>
<tex>n\leftarrow|x|</tex>
<tex>mid\leftarrow?\{1..n\}</tex>
<tex>return</tex> <tex>p(x[1..mid])</tex> <tex>\&\&</tex> <tex>q(x[mid+1..n])</tex>
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<tex>r(x):</tex>
<tex>n\leftarrow|x|</tex>
<tex>prev\leftarrow 1</tex>
<tex>do</tex>
<tex>cur\leftarrow?\{prev..n\}</tex>
<tex>if</tex> <tex>(!p(x[prev..cur]))</tex>
<tex>return</tex> <tex>false</tex>
<tex>prev\leftarrow cur+1</tex>
<tex>while</tex> <tex>(cur</tex> <tex>!=</tex> <tex>n)</tex>
<tex>return</tex> <tex>true</tex>
<br>
}}
=== Примеры NP-языков ===
* Язык раскрасок графа в <tex>k</tex> цветов;
* Язык гамильтоновых графов;
* Задача о клике;
* [http://arxiv.org/abs/cs.CC/0210020 Тетрис]
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. [[Теорема_Ладнера|О существовании не полного <tex>\mathrm{NP}</tex> языка]].
=== Связь P и NP ===
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
*[http://arxiv.org/abs/1011.3944 "решение" 3SAT за полиномиальное время];
*[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжере].
[[Категория: Теория сложности]]
|definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\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\}</tex>.
}}
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
{{Теорема
|statement=
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
|proof=
*<tex>\mathrm{\Sigma_1} \subset \mathrm{NP}</tex>.
Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда сщуествуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
<tex>q(x):</tex>
<tex>y\leftarrow?\{0,1\}^{\le p(|x|)}</tex>
<tex>return</tex> <tex>R(x,y)</tex>
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
Пусть <tex>L\in \mathrm{NP}</tex>. Тогда существует недетерминированная программа <tex>q(x)</tex>, разрешающая этот язык. Построим верификатор <tex>R(x,y)</tex>. В качестве сертификата будем использовать последовательность выборов в программе <tex>q</tex>, приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в <tex>q</tex> может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе <tex>q</tex>, только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если <tex>x\in L</tex>, то в <tex>q</tex> существует последовательность выборов таких, что <tex>q(x)=1</tex>, следовательно существует и верный сертификат. Если <tex>x\notin L</tex>, то для любой последовательности выборов <tex>q(x)=0</tex>, следовательно подходящего сертификата не существует. Таким образом, <tex>L \in \mathrm{\Sigma_1}</tex>.
}}
'''Примечание:'''определение <tex>\mathrm{\Sigma_1}</tex> часто называют также "определением NP на языке сертификатов".
=== Свойства ===
{{Теорема
|statement=
Пусть <tex>L_1,L_2\in \mathrm{NP}</tex>. Тогда:
#<tex>L_1\cap L_2\in \mathrm{NP}</tex>;
#<tex>L_1\cup L_2\in \mathrm{NP}</tex>;
#<tex>L_1L_2\in \mathrm{NP}</tex>;
#<tex>L_1^*\in \mathrm{NP}</tex>.
|proof=
Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
<tex>r(x):</tex>
<tex>return</tex> <tex>p(x)</tex> <tex>\&\&</tex> <tex>q(x)</tex>
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
<tex>r(x):</tex>
<tex>return</tex> <tex>p(x)</tex> <tex>||</tex> <tex>q(x)</tex>
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
<tex>r(x):</tex>
<tex>n\leftarrow|x|</tex>
<tex>mid\leftarrow?\{1..n\}</tex>
<tex>return</tex> <tex>p(x[1..mid])</tex> <tex>\&\&</tex> <tex>q(x[mid+1..n])</tex>
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<tex>r(x):</tex>
<tex>n\leftarrow|x|</tex>
<tex>prev\leftarrow 1</tex>
<tex>do</tex>
<tex>cur\leftarrow?\{prev..n\}</tex>
<tex>if</tex> <tex>(!p(x[prev..cur]))</tex>
<tex>return</tex> <tex>false</tex>
<tex>prev\leftarrow cur+1</tex>
<tex>while</tex> <tex>(cur</tex> <tex>!=</tex> <tex>n)</tex>
<tex>return</tex> <tex>true</tex>
<br>
}}
=== Примеры NP-языков ===
* Язык раскрасок графа в <tex>k</tex> цветов;
* Язык гамильтоновых графов;
* Задача о клике;
* [http://arxiv.org/abs/cs.CC/0210020 Тетрис]
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. [[Теорема_Ладнера|О существовании не полного <tex>\mathrm{NP}</tex> языка]].
=== Связь P и NP ===
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
*[http://arxiv.org/abs/1011.3944 "решение" 3SAT за полиномиальное время];
*[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжере].
[[Категория: Теория сложности]]
