Лекция 5: Проверяющие алгоритмы. Классы NP и NPC

Подробности

Категория: Алгоритмы и модели вычислений

Класс NP. Соотношение между классами P и NP. Существование экспоненциального проверяющего алгоритма для языков из NP. Полиномиальная сводимость. Класс NPC. Способы доказательства NP-полноты.