Схемная сложность: алгоритм для каждого размера входа

Если различаешь размер схемы и её равномерное построение - переходи к «Теперь сам».

Как думаешь: маленькое устройство уже означает быстрый алгоритм?

Для каждого размера файла изготовили устройство, отвечающее на некоторый вопрос. Устройство маленькое, но чертежи выдают отдельно: из чертежа на 100 бит нельзя получить чертёж на 101 бит. Можно ли объявить задачу решённой полиномиальным алгоритмом? Нет: алгоритм обязан одной конечной программой обслуживать все длины входа.

Схемная сложность специально отделяет существование маленького устройства от способа его изготовления. Это полезное усиление модели: нижняя граница для всех маленьких схем автоматически ограничивает и многие обычные алгоритмы, но доказать такую границу обычно труднее.

На что это похоже

Представь завод, который выпускает отдельный жёсткий шаблон для каждой длины детали. Шаблон на 100 отверстий может проверять изделие очень быстро. Если для каждого нового размера надо получить неизвестный чертёж извне, это ещё не единая технология производства шаблонов. Семейство схем описывает шаблоны; равномерность описывает алгоритм, который их строит.

Механизм: схема, семейство и совет

Каждый элемент схемы применяет одну булеву операцию к уже готовым значениям. Циклов нет, поэтому значения вычисляются в топологическом порядке. В последовательной модели просмотр каждого элемента даёт время, линейное по размеру схемы при доступной записи её соединений. Глубина описывает число зависимых слоёв и важна для параллельного вычисления. Малый размер не обязан означать малую глубину.

Функция на n битах имеет 2ⁿ возможных входов. Её можно реализовать схемой, выписав дизъюнкцию всех принимаемых наборов; размер вообще может быть экспоненциальным. Интересны семейства {Cₙ}, где размер каждого Cₙ ограничен одним полиномом от n. Это определение P/poly без требования, что Cₙ эффективно получается по номеру n.

Эквивалентное описание - полиномиальная программа с советом полиномиальной длины, зависящим только от размера входа. Совет не выбирается под конкретный вход: всем строкам длины n выдаётся один и тот же совет. В качестве совета можно передать схему Cₙ; программа вычислит её. Наоборот, фиксировав совет в полиномиальном вычислении, можно получить схему для всех входов данной длины.

P содержится в P/poly: один и тот же полиномиальный алгоритм разворачивается в схемы, причём эффективно. Обратного равенства из определения нет. Неравномерные семейства могут даже кодировать неразрешимую информацию. Для языка, где для каждой длины либо принимаются все строки, либо не принимается ни одна, схема состоит из одной константы. Последовательность этих констант может быть невычислимой. Это не противоречит конечности каждой отдельной схемы: неизвестным остаётся получение бесконечной последовательности схем одной программой.

Для CIRCUIT-SAT входом служит сама конечная схема. Спрашивается, есть ли набор входных битов с выходом один. Принадлежность NP ясна: набор - сертификат, схема вычисляется за полиномиальное время. Для трудности берут проверяющую программу произвольного языка NP. Её полиномиально длинное вычисление кодируется последовательностью состояний и логическими связями между соседними шагами. Вход задачи закреплён константами, биты сертификата свободны. Получившаяся схема выполнима ровно для входов, у которых есть принимаемый сертификат. Это схемный путь к теореме Кука-Левина; он не предполагает, что схему уже научились решать быстро.

Правило

P/poly ограничивает размер отдельной схемы на каждой длине, а P требует единую эффективную программу. CIRCUIT-SAT спрашивает о существовании набора для данной схемы; обычное вычисление схемы на данном наборе - другая, лёгкая задача.

Разбор: вычислить схему и найти набор

В файле записана схема условия: ровно два из трёх входов равны единице. Узел хранит операцию и номера источников. У входа номер меньше, чем у элементов схемы; значения добавляются в список по порядку, поэтому ссылка назад уже вычислена.

from itertools import product


def vychislit(vhod, shema):
    z = list(vhod)
    for op, a, b in shema:
        if op == 'AND':
            z.append(z[a] and z[b])
        elif op == 'OR':
            z.append(z[a] or z[b])
        elif op == 'NOT':
            z.append(not z[a])
        else:
            raise ValueError(op)
    return bool(z[-1])


shema = [
    ('AND', 0, 1),     # 3: x и y
    ('AND', 0, 2),     # 4: x и z
    ('AND', 1, 2),     # 5: y и z
    ('OR', 3, 4),      # 6
    ('OR', 6, 5),      # 7: хотя бы два
    ('AND', 3, 2),     # 8: все три
    ('NOT', 8, 8),     # 9: не все три
    ('AND', 7, 9),     # 10: ровно два
]
resheniya = []
for bits in product([False, True], repeat=3):
    otvet = vychislit(bits, shema)
    if otvet:
        resheniya.append(''.join(str(int(x)) for x in bits))
print('элементов:', len(shema))
print('подходящие наборы:', *resheniya)
print('проверка 110:', vychislit([True, True, False], shema))
print('проверка 111:', vychislit([True, True, True], shema))

элементов: 8
подходящие наборы: 011 101 110
проверка 110: True
проверка 111: False

Проверка 110 делает восемь вычислений элементов. Поиск всех подходящих наборов просмотрел восемь входов и на каждом вычислил схему. При n входах число наборов станет 2ⁿ, хотя сама схема может расти полиномиально. Перебор здесь показывает разницу задач, но не доказывает невозможность более быстрого поиска.

Разбор: один совет для всей длины

Пусть задача на строках длины десять требует один секретный бит b₁₀. Совет из одного бита позволяет отвечать на все 1024 входа этой длины одинаково. Это разрешено. Совет «правильный ответ для поступившей строки» запрещён: он зависит от самой строки, а не только её длины. Если же задача требует произвольную таблицу всех 1024 ответов, совет может быть слишком большим при обобщении на длину n: таблица содержит 2ⁿ бит.

Что ломается без этого

Оптимизированный чип на фиксированное число битов не доказывает принадлежность всей задачи P. Построение маленьких схем для нескольких первых длин не даёт семейство с одной полиномиальной границей. Ссылка «проверка схемы линейна» не решает CIRCUIT-SAT: на входе поиска отсутствует набор, который надо проверить.

Зачем это в работе

Компилятор может специализировать программу под фиксированную длину данных, криптографическая реализация - под ширину блока. Схемы позволяют отдельно считать количество операций и зависимую глубину. В теории криптографии неравномерный противник моделирует дополнительные знания, полученные заранее; важно, что объём такого совета ограничен и он общий для всех входов данной длины.

Теперь сам

Дана схема из 1000 элементов с 40 входами и конкретный набор входных битов. Требует ли её вычисление перебора 2⁴⁰ наборов? Что меняется, если нужно установить существование принимаемого набора?