Классы NP, coNP, Σ₁, Π₁ — различия между версиями
(→Связь P и NP) |
|||
Строка 7: | Строка 7: | ||
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время. | То есть <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>. | + | |definition=<tex>\mathrm{\Sigma_1}=\{L\bigm|\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>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором. | Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором. |
Версия 17:21, 4 июня 2012
Тут должен быть заголовок.
NP и Σ₁
Определение: |
. |
То есть
— это множество языков, разрешимых недетерминированной программой за полиномиальное время.Определение: |
. |
Нестрого говоря,
— это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор , а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.Теорема: |
. |
Доказательство: |
Пусть . Тогда существуют и полином из определения . Построим недетерминированную программу , разрешающую .Если , то программа сможет «угадать» подходящий сертификат. Если , то подходящего сертификата не существует по определению. Таким образом, разрешает , следовательно .
|
Примечание:определение
часто называют также «определением NP на языке сертификатов».Свойства
Теорема: |
Пусть . Тогда:
|
Доказательство: |
Пусть разрешает , а разрешает .1. Построим программу , разрешающую :2. Построим программу , разрешающую :3. Построим программу , разрешающую :4. Построим программу , разрешающую : |
Примеры NP-языков
- Язык раскрасок графа в цветов;
- Язык гамильтоновых графов;
- Задача о клике;
- Тетрис
Все эти языки также являются . -полнымиО существовании не полного . языка
Связь P и NP
Очевидно, что редкий ; было доказано, что -полный языкдоказательство должно быть нерелятивизующимся; различные попытки найти полиномиальные решения для задач из :
, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найтиНекоторые задачи из
очень похожи на задачи из . В каждой из приведенных ниже задач пар задач одна разрешима за полиномиальное время, а другая является -полной. При этом различие между задачами кажется совершенно незначительным.- Поиск самых коротких и самых длинных простых путей;
- Эйлеров и гамильтонов циклы;
- 2-CNF и 3-CNF выполнимость.