Сводимость по Куку в теории алгоритмов¶

Сводимость по Куку — одно из центральных понятий теории сложности вычислений, определяющее отношение между задачами, при котором одна задача может быть решена за полиномиальное время с использованием оракула, отвечающего на запросы другой задачи. Это понятие было введено американским математиком и информатиком Стивеном Куком в 1971 году в его основополагающей работе, посвящённой NP-полноте, и является формализацией идеи «не сложнее, чем» в контексте классов сложности P и NP.

¶Определение

Формально, задача (или язык) A сводится по Куку к задаче B (обозначается \( A \leq_T^P B \)), если существует детерминированная машина Тьюринга с полиномиальным временем работы, которая имеет доступ к оракулу для задачи B и решает задачу A. Такая машина называется машиной с оракулом, а сам процесс — полиномиальной сводимостью по Тьюрингу.

Ключевое отличие сводимости по Куку от более строгой сводимости по Карпу (или сводимости «много-один») заключается в том, что машина может обращаться к оракулу многократно и адаптивно: каждый следующий запрос к оракулу может зависеть от ответов на предыдущие запросы. При сводимости по Карпу допускается только один запрос к оракулу в конце вычисления, и ответ оракула напрямую определяет ответ исходной задачи. Таким образом, сводимость по Куку является более слабым (более общим) отношением: любая сводимость по Карпу автоматически является сводимостью по Куку, но обратное неверно.

¶Свойства

Сводимость по Куку обладает рядом важных свойств, делающих её удобным инструментом в теории сложности:

• Рефлексивность: любая задача сводится по Куку к самой себе (достаточно просто использовать оракул без изменений).
• Транзитивность: если \( A \leq_T^P B \) и \( B \leq_T^P C \), то \( A \leq_T^P C \). Это свойство позволяет строить цепочки сведения и упорядочивать задачи по сложности.
• Замкнутость классов: если класс сложности замкнут относительно полиномиального времени и задача B принадлежит этому классу, то любая задача A, сводимая к B по Куку, также принадлежит этому классу. В частности, если \( A \leq_T^P B \) и \( B \in P \), то \( A \in P \).

Благодаря транзитивности и замкнутости, сводимость по Куку используется для определения класса NP-эквивалентных задач — задач, которые сводятся по Куку друг к другу. Этот класс шире, чем класс NP-полных задач, определённый через сводимость по Карпу.

¶Связь с NP-полнотой

В оригинальной работе Стивена Кука 1971 года «Сложность процедур доказательства теорем» NP-полнота определялась именно через сводимость по Куку. Кук показал, что задача выполнимости булевых формул (SAT) является NP-полной в том смысле, что любая задача из класса NP сводится к ней по Куку за полиномиальное время. Это был первый доказанный пример NP-полной задачи.

Позднее, в 1972 году, Ричард Карп предложил более строгое определение NP-полноты на основе сводимости «много-один» (сводимости по Карпу) и продемонстрировал NP-полноту 21 комбинаторной задачи. Определение Карпа стало стандартным в учебной литературе, поскольку оно удобнее для доказательств и даёт более точную классификацию внутри класса NP. Тем не менее, сводимость по Куку остаётся важным инструментом, особенно при обсуждении задач, для которых неизвестна сводимость по Карпу, но известна сводимость по Куку.

¶Значение и применение

Сводимость по Куку играет фундаментальную роль в теории сложности вычислений по нескольким причинам:

• Сравнение сложности задач: она позволяет формально утверждать, что одна задача не сложнее другой, даже если их точная вычислительная сложность неизвестна.
• Исследование классов сложности: понятие используется при изучении классов \( P \), \( NP \), \( PSPACE \) и других. Например, задачи, полные для класса \( PSPACE \), часто определяются через сводимость по Куку.
• Теория оракулов: сводимость по Куку тесно связана с концепцией релятивизации — рассмотрения вычислений с оракулами. Результаты, полученные для машин с оракулами, помогают понять ограничения методов доказательства в теории сложности (например, невозможность решения вопроса \( P \) vs \( NP \) с помощью диагонализации).

На практике сводимость по Куку используется в тех случаях, когда сведение по Карпу построить не удаётся или оно неизвестно. Например, для задачи о клике и задачи о независимом множестве существует простое взаимное сведение по Куку, хотя сводимость по Карпу также существует. Однако для некоторых задач, таких как задача распознавания простых чисел (до открытия теста Агравала — Кайала — Саксены в 2002 году), сводимость по Куку была известна, в то время как сводимость по Карпу оставалась открытым вопросом.

¶Критика и ограничения

Основное ограничение сводимости по Куку связано с её «небрежностью» в отношении структуры вычислений. Поскольку машина может делать множество адаптивных запросов, она может использовать оракул нетривиальным образом, что иногда приводит к «неестественным» сведениям. Например, задача, которая сводится по Куку к задаче \( B \), может не сводиться к ней по Карпу, что затрудняет точную классификацию задач внутри класса NP. Кроме того, сводимость по Куку не различает задачи, которые решаются за полиномиальное время с одним запросом к оракулу, и задачи, требующие экспоненциального числа запросов (хотя последнее уже выходит за рамки полиномиального времени).

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

¶Источники

• Стивен Кук. «Сложность процедур доказательства теорем» (1971).
• Ричард Карп. «Сводимость комбинаторных задач» (1972).
• Кристофер Пападмитриу. «Вычислительная сложность» (1994).
• Санджив Арора, Боаз Барак. «Вычислительная сложность: современный подход» (2009).