Изменения

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

Классы NP, coNP, Σ₁, Π₁

136 байт убрано, 23:21, 31 марта 2016
→‎Примеры языков из NP: Добавил простой пример, удалил пример про клики
== Примеры языков из NP ==
=== Язык палиндромов ===
Этот язык разрешается автоматом с магазинной памятью, то есть принадлежит <tex>\mathrm P</tex>, а следовательно, и <tex>\mathrm{NP}</tex>.
=== Язык задачи о раскраске вершин графа в <tex>k</tex> цветов ===
{{main|Раскраска графа}}
'''if''' <tex>p[i]p[i + 1] \notin E(G)</tex>
'''return''' ''false''
'''return''' ''true''
=== Задача о клике ===
<tex>r(G)\colon</tex>
n = <tex>|V(G)|</tex>
c <tex>\gets? \{ 0, 1 \} ^ n</tex>
'''for''' <tex>u</tex> '''in''' <tex>V(G)</tex>
'''for''' <tex>v</tex> '''in''' <tex>V(G)</tex>
'''if''' <tex>u \ne v</tex> '''and''' <tex>c[u]</tex> '''and''' <tex>c[v]</tex> '''and''' <tex>uv \notin E(G)</tex>
'''return''' ''false''
'''return''' ''true''
Все эти языки Два последних языка также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], если <tex>\mathrm{P \ne NP}</tex>, то существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
== Примеры языков из coNP ==
Iloskutov
130
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/52993»

Навигация