Введение

Метод решения одной задачи с помощью другой

В теории вычислительной сложности, полиномиальное сведение по времени — это метод решения одной задачи, используя другую. Доказывается, что если существует гипотетическая подпрограмма для решения второй задачи, то первую задачу можно решить, преобразовав её во входные данные для второй задачи и вызвав эту подпрограмму один или несколько раз. Если время, необходимое для преобразования первой задачи во вторую, и количество вызовов подпрограммы являются полиномиальными, то первая задача полиномиально сводится ко второй. Полиномиальное сведение по времени доказывает, что первая задача не сложнее второй, поскольку при наличии эффективного алгоритма для второй задачи, эффективный алгоритм существует и для первой. От противного, если для первой задачи не существует эффективного алгоритма, то не существует и для второй. Наиболее общими сведениями являются сведения Тьюринга, а наиболее строгими — сведения «многие к одному», при этом сведения по таблице истинности занимают промежуточное положение.

Снижение на множественном

Многочленное по времени сведение от задачи А к задаче В (обе задачи, как правило, должны быть задачами принятия решений) — это алгоритм, работающий за полиномиальное время, для преобразования входных данных задачи А во входные данные задачи В таким образом, что преобразованная задача имеет тот же результат, что и исходная задача. Экземпляр x задачи А можно решить, применив это сведение для получения экземпляра y задачи В, передав y на вход алгоритму для задачи В и вернув его результат. Сведения многочленного времени также могут быть известны как полиномиальные преобразования или сведение Карпа, названное в честь Ричарда Карпа. Такое сведение обозначается ≤m или ≼m.

Снижение по Тьюрингу

Полиномиальное по времени редуцирование Тьюринга от задачи A к задаче B — это алгоритм, решающий задачу A, используя полиномиальное количество вызовов подпрограммы для задачи B и полиномиальное время вне этих вызовов подпрограммы. Полиномиальные по времени редуцирования также известны как редуцирования Кука, названные в честь Стивена Кука. Редуцирование такого типа может быть обозначено выражением "полиномиальное по времени". Многие-к-одному редуцирования в полиномиальное время используются для определения полных задач для других классов сложности, включая полные языки PSPACE и полные языки EXPTIME. Каждая задача принятия решения в P (классе задач принятия решения в полиномиальное время) может быть сведена к каждой другой нетривиальной задаче принятия решения (где нетривиальность означает, что не для каждого входа выход одинаков), посредством редуцирования многие-к-одному в полиномиальное время. Чтобы преобразовать экземпляр задачи A в экземпляр задачи B, решите A в полиномиальное время, а затем используйте решение для выбора одного из двух экземпляров задачи B с разными ответами. Следовательно, для классов сложности, содержащихся в P, таких как L, NL, NC и сам P, полиномиальные по времени редуцирования не могут быть использованы для определения полных языков: если бы они использовались таким образом, каждая нетривиальная задача в P была бы полной. Вместо этого для определения классов полных задач для этих классов используются более слабые редуцирования, такие как логарифмические по пространству редуцирования или NC-редуцирования, например, полные задачи P.

Определение классов сложности

Определения классов сложности NP, PSPACE и EXPTIME не включают в себя редукции: редукции начинают изучаться только при определении полных языков для этих классов. Однако в некоторых случаях класс сложности может быть определен с помощью редукций. Если C – это любая задача принятия решения, то можно определить класс сложности C, состоящий из языков A, для которых в этом случае C автоматически будет полным для C, но C может иметь и другие полные задачи. Примером этого является класс сложности, определенный на основе экзистенциальной теории вещественных чисел – вычислительная задача, известная как NP-трудная и принадлежащая классу PSPACE, но не являющаяся полной для NP, PSPACE или какого-либо языка в полиномиальной иерархии. Это множество задач, имеющих полиномиальную редукцию к экзистенциальной теории вещественных чисел; оно содержит несколько других полных задач, таких как определение числа пересечений на плоскости для неориентированного графа. Каждая задача из этого множества наследует свойство принадлежности к PSPACE, и каждая полная задача является NP-трудной. Аналогично, класс сложности GI состоит из задач, которые могут быть сведены к задаче об изоморфизме графов. Поскольку задача об изоморфизме графов принадлежит как NP, так и co AM, то же самое верно для каждой задачи в этом классе. Задача является GI-полной, если она полна для этого класса; сама задача об изоморфизме графов является GI-полной, как и несколько других связанных задач.