== Примеры языков из NP ==
* === Проблема раскраски вершин графа в <tex>k</tex> цветов.<br><!--===-->Разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин время: <tex>r(G):\colon</tex>
n = <tex>|V(G)|</tex>
c =<suptex>\gets?</sup> <tex>\{ 1, \dotsc, k \} ^ n</tex> '''for''' <tex>uv </tex> '''in''' <tex>E(G)</tex>
'''if''' c[u] == c[v]
'''return''' ''false''
'''return''' ''true''
* === Проблема нахождения гамильтонова цикла:=== <tex>r(G):\colon</tex> n = <tex>|V(G)|</tex> p =<suptex>\gets?</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''' <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> '''not 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-полнота игры Тетрис|Тетрис]].Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], если <tex>\mathrm{P \ne NP}</tex>, то существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
== Примеры языков из coNP ==
