171
правка
Изменения
м
Нет описания правки
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\mathrm{\Sigma_1}=\{L|\exists R(x,y)\in \tilde{\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>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
|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>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 на языке сертификатов"сертификатов».
=== Свойства ===
=== Связь 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 задача о коммивояжере].
