130
правок
Изменения
→Проблема раскраски вершин графа в k цветов: переформулировал в терминах принадлежности языку, пофиксил время работы
== Примеры языков из NP ==
=== Проблема раскраски Задача о раскраске вершин графа в <tex>k</tex> цветов ===Разрешается Переформулируем задачу в терминах принадлежности языку: пусть <tex> L = \{ \langle G, k \rangle \mid </tex> вершины <tex>G</tex> можно раскрасить в <tex>k</tex> цветов <tex>\}</tex>. Этот язык разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин и рёбер время: <tex>r(\langle G, k \rangle)\colon</tex>
<tex>n = |V(G)|</tex>
<tex>c \gets?\ \{ 1, \dotsc, k \} ^ n</tex>
