Редактирование: Классы NP, coNP, Σ₁, Π₁

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Определения, связь Σ₁ и NP ==
 
== Определения, связь Σ₁ и NP ==
 
{{Определение
 
{{Определение
|id=def1
+
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\!\!\operatorname{NTIME}(p(n))</tex>.
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in \mathit{poly}}\!\!\operatorname{NTIME}(p(n))</tex>.
 
 
}}
 
}}
 
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время.
 
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой]] за полиномиальное время.
Строка 10: Строка 9:
 
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в <tex>\mathrm{NP}</tex>.
 
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в <tex>\mathrm{NP}</tex>.
 
{{Определение
 
{{Определение
|definition=<tex>\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in \mathit{poly} : x\in L\Leftrightarrow\exists y : |y|\leqslant p(|x|), R(x,y)=1\}</tex>.
+
|definition=<tex>\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\}</tex>.
 
}}
 
}}
 
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
 
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
 
{{Определение
 
{{Определение
|definition=<tex>\mathrm{\Pi_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in \mathit{poly} : x\in L\Leftrightarrow\forall y : |y|\leqslant p(|x|), R(x,y)=1\}</tex>.
+
|definition=<tex>\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\}</tex>.
 
}}
 
}}
 
То есть <tex>\Pi_1</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) нельзя предъявить сертификат длины, ограниченной неким полиномом, опровергающий принадлежность слова языку и проверяемый верификатором. Легко видеть, что <tex>\Pi_1</tex> — множество языков, дополнения к которым лежат в <tex>\Sigma_1</tex>.
 
То есть <tex>\Pi_1</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) нельзя предъявить сертификат длины, ограниченной неким полиномом, опровергающий принадлежность слова языку и проверяемый верификатором. Легко видеть, что <tex>\Pi_1</tex> — множество языков, дополнения к которым лежат в <tex>\Sigma_1</tex>.
Строка 44: Строка 43:
 
Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
 
Пусть <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> за полиномиальное время:
+
:1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
 
  <tex>r(x)\colon</tex>
 
  <tex>r(x)\colon</tex>
 
   '''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
 
   '''return''' <tex>p(x)</tex> '''and''' <tex>q(x)</tex>
:2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex> за полиномиальное время:
+
:2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
 
  <tex>r(x)\colon</tex>
 
  <tex>r(x)\colon</tex>
 
   '''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
 
   '''return''' <tex>p(x)</tex> '''or''' <tex>q(x)</tex>
:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex> за полиномиальное время:
+
:3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
 
  <tex>r(x)\colon</tex>
 
  <tex>r(x)\colon</tex>
 
   <tex>n = |x|</tex>
 
   <tex>n = |x|</tex>
 
   <tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
 
   <tex>mid \gets?\ \{1 \mathinner{\ldotp\ldotp} n\}</tex>
 
   '''return''' <tex>p(x[1 \mathinner{\ldotp\ldotp} mid])</tex> '''and''' <tex>q(x[mid+1 \mathinner{\ldotp\ldotp} n])</tex>
 
   '''return''' <tex>p(x[1 \mathinner{\ldotp\ldotp} mid])</tex> '''and''' <tex>q(x[mid+1 \mathinner{\ldotp\ldotp} n])</tex>
:4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex> за полиномиальное время:
+
:4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
 
  <tex>r(x)\colon</tex>
 
  <tex>r(x)\colon</tex>
 
   <tex>n = |x|</tex>
 
   <tex>n = |x|</tex>
Строка 121: Строка 120:
 
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
 
!Принадлежит <tex>\mathrm P</tex>||<tex>\mathrm{NP}</tex>-полная
 
|-
 
|-
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||Поиск самых длинных простых путей<ref>[//en.wikipedia.org/wiki/Longest_path_problem Longest path problem - Wikipedia]</ref>
+
|[[Обход_в_ширину|Поиск самых коротких простых путей]]||[//en.wikipedia.org/wiki/Longest_path_problem Поиск самых длинных простых путей]
 
|-
 
|-
|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл]]||[[NP-полнота задач о гамильтоновом цикле и пути в графах|Гамильтонов цикл]]
+
|[[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл]]||[[Гамильтоновы_графы|Гамильтонов цикл]]
 
|-
 
|-
 
|[[2SAT|2-CNF выполнимость]]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость]]
 
|[[2SAT|2-CNF выполнимость]]||[[Примеры NP-полных языков#NP-полнота 3-SAT|3-CNF выполнимость]]
 
|}
 
|}
 +
  
 
== См. также ==
 
== См. также ==
Строка 134: Строка 134:
 
<references/>
 
<references/>
  
[[Категория: Классы сложности]]
+
[[Категория: Теория сложности]]
 
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ]]
 
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ]]
 
[[Категория: Классы P и NP, NP-полнота]]
 
[[Категория: Классы P и NP, NP-полнота]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: