Сводимость задач

Сводимость — рычаг, которым одну доказанную неразрешимость превращают в десятки новых. «Если бы ты решил B, ты бы решил и неразрешимую A».

Сводимость A к B (A ≤ B): преобразование задачи A в задачу B такое, что решение B давало бы решение A. Если A неразрешима, то и B неразрешима.

Идея редукции

Доказывать каждую неразрешимость диагональю утомительно. Сводимость даёт ленивый, но строгий путь: чтобы показать неразрешимость новой задачи B, достаточно свести к ней уже известную неразрешимую задачу A (обычно — проблему остановки). Логика: предположим, B разрешима алгоритмом R_B. Построим из него алгоритм для A, переведя любой вход A в подходящий вход B и спросив R_B. Тогда A стала бы разрешимой — противоречие, ведь A неразрешима. Значит, B неразрешима.

редукция A ≤ B:

  вход a  ──[преобразование f]──►  вход f(a) для B
                                        │
                                   R_B решает B
                                        │
                                   ответ ──► это и ответ для A

если R_B существует ⇒ A разрешима ⇒ противоречие (A неразрешима)
⇒ R_B не существует ⇒ B неразрешима

Пример: «печатает ли программа 42»

Задача: по программе определить, выведет ли она когда-нибудь число 42. Покажем неразрешимость сведением проблемы остановки. Дано (M, w). Строим программу P: «симулируй M на w; если M остановилась — напечатай 42». Тогда P печатает 42 ⇔ M останавливается на w. Если бы мы умели решать «печатает ли 42», мы бы решили проблему остановки — но она неразрешима. Значит, и «печатает ли 42» неразрешима. Никакого нового диагонального аргумента — мы переиспользовали готовый.

Демонстрация механики редукции

Смоделируем редукцию на «игрушечных» задачах (с лимитом, чтобы код завершался): построим из «решателя B» решатель A, преобразовав вход. Это иллюстрирует структуру редукции, а не настоящую неразрешимость.

# задача B: "равна ли сумма цифр числа нулю по модулю 3?"
def solver_B(n):
    return sum(int(d) for d in str(abs(n))) % 3 == 0

# задача A: "делится ли число на 3?" сводим к B
# редукция f: для A число n уже годится как вход B
# (известно: делимость на 3 == сумма цифр делится на 3)
def solver_A_via_B(n):
    reduced_input = n          # f(n) = n
    return solver_B(reduced_input)   # вызываем решатель B

for n in [12, 7, 99, 100, 33]:
    print(f"{n:>4}: A(делится на 3)={solver_A_via_B(n)}  проверка={n % 3 == 0}")

Вывод:

  12: A(делится на 3)=True  проверка=True
   7: A(делится на 3)=False  проверка=False
  99: A(делится на 3)=True  проверка=True
 100: A(делится на 3)=False  проверка=False
  33: A(делится на 3)=True  проверка=True

Решатель A целиком построен поверх решателя B через преобразование входа. Если бы B был «всемогущим оракулом», A получил бы его силу бесплатно — ровно эта логика и переносит неразрешимость с задачи на задачу.

Как работает под капотом

Сводимость — несущая конструкция всей теории неразрешимости и сложности. В вычислимости через редукции от проблемы остановки доказывают неразрешимость десятков задач: эквивалентность программ, пустота языка машины, проблема соответствий Поста, десятая проблема Гильберта (решение диофантовых уравнений). В теории сложности тот же приём с полиномиальными редукциями определяет NP-полноту (следующий раздел): задача NP-полна, если к ней сводится любая задача из NP. Сводимость — универсальный способ переносить трудность.

Частые ошибки

Перепутать направление редукции. Чтобы доказать неразрешимость B, сводят известную неразрешимую A к B (A ≤ B), а не наоборот. Направление критично — ошибка обессмысливает доказательство.

Делать преобразование, которое само неразрешимо. Функция-редукция f должна быть вычислимой (для сложности — за полином), иначе редукция нелегальна.

Думать, что редукция решает обе задачи. Редукция лишь связывает их трудность; она не решает неразрешимую A, а доказывает, что B не легче A.

Итог

Сводимость A ≤ B: вход A вычислимо преобразуется во вход B так, что ответ B даёт ответ A.
Если A неразрешима и A ≤ B, то B неразрешима — переиспользуем готовое доказательство.
Через редукции от проблемы остановки доказана неразрешимость множества задач (эквивалентность программ, ПСП и др.).
Тот же приём с полиномиальными редукциями лежит в основе NP-полноты.