Конспект: P, NP, сведения и NP-полнота

Понятия

Задача разрешения - вопрос с ответом «да» или «нет». Длина входа - число бит его записи.

Класс P - задачи, решаемые за время не больше c · nᵏ. Класс NP - задачи, у которых ответ «да» подтверждается сертификатом полиномиальной длины и полиномиальной проверяющей программой. co-NP - то же для ответа «нет».

КНФ - «и» скобок, в скобке «или» литералов (переменная или её отрицание). SAT - выполнима ли формула. 3-SAT - то же, скобки не длиннее трёх литералов.

Полиномиальное сведение A ≤ B - быстрый перевод входов A во входы B с тем же ответом.

NP-трудная задача - к ней сводится всё из NP. NP-полная - NP-трудная и сама в NP.

Независимое множество - вершины без рёбер между ними. Вершинное покрытие - вершины, задевающие каждое ребро. Клика - вершины, попарно соединённые.

Что унести

ВРЕМЯ, миллиард (для простоты счёта 2³⁰) операций в секунду
n          n²                 n⁵                 2ⁿ
40         меньше секунды     меньше секунды     17 минут
60         меньше секунды     меньше секунды     34 года
80         меньше секунды     3 с                35 миллионов лет
1000       меньше секунды     258 часов          -
удвоение входа:  nᵏ растёт в 2ᵏ раз;  2ⁿ возводится в квадрат
железо в 1000 раз быстрее: +10 к n

длина входа - биты записи:  число N занимает log₂ N бит
перебор делителей до √N:    бит        20      24       28
                            проверок   1022    4094     16382
                            2 в степени половины длины

NP: предъявить и проверить
задача                  сертификат           проверка
SAT                     значения переменных  подставить
цикл через все вершины  порядок вершин       каждая один раз, рёбра есть
сумма подмножества      номера чисел         сложить
составное число         делитель             разделить

P ⊆ NP ⊆ EXP;   P ≠ EXP доказано;   P = NP? и NP = co-NP? - неизвестно
проверить набор - длина формулы;   найти перебором - 2ⁿ наборов:
                                   16, 256, 1024 при n = 4, 8, 10
о сертификатах ответа «нет» определение ничего не обещает

СВЕДЕНИЕ  A ≤ B:  перевод полиномиален,  «да» → «да»,  «нет» → «нет»
B в P  →  A в P        A трудна  →  B трудна        A ≤ B ≤ C  →  A ≤ C

независимое множество размера k  ⇄  вершинное покрытие размера n − k
                                    (граф тот же)
независимое множество в G        ⇄  клика в дополнении G   (k то же)
вершинное покрытие ≤ покрытие множествами:
    элементы - рёбра, множество вершины - её рёбра
граф на 7 вершинах:  независимых 4, покрытие 3,
                     клика в дополнении - те же 4 вершины

NP-ПОЛНОТА
Кук-Левин:  проверка V(x, c)  →  схема из вентилей  →  формула;
            сертификат = переменные
    g = a и b       (¬g ∨ a) (¬g ∨ b) (g ∨ ¬a ∨ ¬b)
    g = a или b     (g ∨ ¬a) (g ∨ ¬b) (¬g ∨ a ∨ b)
    голосование из трёх:  5 вентилей, 16 скобок, 4 выполняющих набора

SAT ≤ 3-SAT:  (a ∨ b ∨ c ∨ d ∨ e)
              →  (a ∨ b ∨ y₁) (¬y₁ ∨ c ∨ y₂) (¬y₂ ∨ d ∨ e)
              k литералов  →  k − 2 скобки, k − 3 новые переменные;
              2-SAT лежит в P

3-SAT ≤ независимое множество:
    вершина - вхождение литерала;   рёбра внутри скобки;
    рёбра между x и ¬x из разных скобок
    k = число скобок;   между одинаковыми литералами рёбер НЕТ
    3 скобки по 3 литерала:  9 вершин, 9 + 6 = 15 рёбер

доказать NP-полноту B:   1) B в NP;
                         2) известную NP-полную задачу свести к B

Ловушки джокера

Посчитал время от величины числа. Цикл до N - экспонента от длины записи N.

Прочитал NP как «неполиномиальные». В NP лежит весь P.

Счёл полиномиальный алгоритм быстрым. n⁵ на тысяче элементов - одиннадцать суток.

Принял один негодный сертификат за ответ «нет». Так доказывается только «этот сертификат не подошёл».

Свёл свою задачу к SAT, чтобы показать её трудность. К SAT сводится и сортировка. Направление обратное.

Доказал одну половину сведения. Без «нет → нет» перевод может превращать невыполнимое в выполнимое.

Назвал NP-полную задачу неразрешимой или доказанно медленной. Она разрешима; медленность не доказана - доказана равносильность вопросу о P и NP.

Соединил одинаковые литералы в графе сведения. Запрещать нужно только x вместе с ¬x.

Решил, что NP-полная задача трудна на каждом входе. Оценка - для худшего случая.

Проверь себя

Почему граница проведена по многочлену и в чём измеряется вход? Что такое сертификат и почему у ответа «нет» его может не быть? Что следует из A ≤ B в каждую сторону? Как проверка превращается в формулу? Какие два шага доказывают NP-полноту новой задачи? Какие рёбра в графе сведения от 3-SAT и зачем каждое?

RP ошибается только отказом, coRP только принятием, BPP допускает обе ошибки. ZPP = RP ∩ coRP: верный ответ с полиномиальным ожидаемым временем.

P/poly - семейства полиномиальных схем без требования равномерности; совет зависит только от длины входа. Вычисление готовой схемы легко, CIRCUIT-SAT NP-полна.

IP: полиномиальный случайный проверяющий и неограниченный доказывающий, полнота и звуковость. IP = PSPACE. В протоколе неизоморфизма источник переименованного графа скрыт.

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий