130
правок
Изменения
→Примеры языков из NP: добавил ссылки на основные статьи для примеров, добавил больше теха в псевдокод
== Примеры языков из NP ==
=== Задача Язык задачи о раскраске вершин графа в <tex>k</tex> цветов ==={{main|Раскраска графа}}
Переформулируем задачу в терминах принадлежности языку: пусть <tex> L = \{ \langle G, k \rangle \mid </tex> вершины <tex>G</tex> можно раскрасить в <tex>k</tex> цветов <tex>\}</tex>.
'''return''' ''true''
=== Проблема нахождения гамильтонова цикла Язык гамильтоновых графов ==={{main|Гамильтоновы графы}}
<tex>r(G)\colon</tex>
'''return''' ''false''
<tex>p[n + 1] = p[1]</tex> '''for''' <tex>i = 1 </tex> '''to''' <tex>n</tex>
'''if''' <tex>p[i]p[i + 1] \notin E(G)</tex>
'''return''' ''false''
