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