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

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







Видеотека

Яндекс.Метрика