38
правок
Изменения
Нет описания правки
Мы рассмотрим некоторые языки и докажем их '''NP'''-полноту. Начнем мы с языка <tex> \mathrm{BH_{1N}} </tex>, так как к нему несложно сводятся все языки из '''NP'''.
Потом с помощью [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведений по Карпу ]] будем сводить уже известные языки из '''NPC''' к новым языкам, тем самым доказывая их '''NP'''-трудность, а потом и '''NP'''-полноту.
Доказательство '''NP'''-полноты будет состоять из двух пунктов: доказательство '''NP'''-трудности и принадлежности языка классу '''NP'''.
=== NP-полнота задачи о рюкзаке ===
== Ссылки ==
* [[Класс P]]
* [[Недетерминированные вычисления. Классы NP и Σ₁]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
[[Категория: Теория сложности]]
