130
правок
Изменения
→Язык гамильтоновых графов: добавил пояснение про время работы
=== Язык гамильтоновых графов ===
{{main|Гамильтоновы графы}}
Рассмотрим следующий язык: <tex>L = \{ G \mid G</tex> — гамильтонов граф<tex>\}</tex>. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:
<tex>r(G)\colon</tex>
<tex>n = |V(G)|</tex>
