130
правок
Изменения
→Примеры языков из NP: добавил (с доказательством) задачу о гамильтоновом цикле
'''return''' ''false''
'''return''' ''true''
* Проблема нахождения гамильтонова цикла:
r(G):
n = <tex>|V(G)|</tex>
p =<sup>?</sup> <tex>V(G) ^ n</tex>
'''for''' i = 1 '''to''' n
'''if''' v[i] '''not in''' p
'''return''' ''false''
p[n + 1] = p[1]
'''for''' i = 1 '''to''' n
'''if''' p[i]p[i + 1] '''not in''' <tex>E(G)</tex>
'''return''' ''false''
'''return''' ''true''
* Задача о клике.
* [http://arxiv.org/abs/cs.CC/0210020 [NP-полнота игры Тетрис|Тетрис]].Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]] , существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
== Примеры языков из co-NP ==
