Редукция за полиномиальное время - Polynomial-time reduction

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

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

Виды скидок

Три наиболее распространенные типы сокращения полиномиальное время, от наиболее к наименее ограничивающим, являются полиномиальное время многие-одно сокращение , сокращение истинности таблиц и сокращения Тьюринга . Наиболее часто используемыми из них являются сокращения «многие-один», и в некоторых случаях фраза «полиномиальное сокращение» может использоваться для обозначения полиномиального сокращения «многие-один». Наиболее общие редукции - это редукции по Тьюрингу, а наиболее строгие - редукции по принципу «много-один» с редукциями по таблице истинности, занимающими промежуточное пространство.

Скидки на несколько единиц

Редукция многих единиц за полиномиальное время от проблемы A к проблеме B (обе из которых обычно требуются как задачи решения ) представляет собой алгоритм с полиномиальным временем преобразования входных данных в проблему A во входные данные в проблему B , так что преобразованные проблема имеет тот же результат, что и исходная проблема. Экземпляр x проблемы A может быть решен путем применения этого преобразования для создания экземпляра y проблемы B , предоставления y в качестве входных данных для алгоритма для проблемы B и возврата его выходных данных. Полиномиальные преобразования " много-один" могут также называться полиномиальными преобразованиями или редукциями Карпа , названными в честь Ричарда Карпа . Редукция этого типа обозначается или . ${\ Displaystyle A \ leq _ {m} ^ {P} B}$${\ displaystyle A \ leq _ {p} B}$

Сокращения таблицы истинности

Редукция таблицы истинности за полиномиальное время от проблемы A к проблеме B (обе задачи решения) - это алгоритм с полиномиальным временем для преобразования входных данных к задаче A в фиксированное количество входов для задачи B , так что выход для исходной задачи может быть выражен в виде функции выходов для B . Функция, которая сопоставляет выходы для B с выходом для A, должна быть одинаковой для всех входов, чтобы ее можно было выразить таблицей истинности . Редукцию этого типа можно обозначить выражением . ${\ Displaystyle A \ leq _ {tt} ^ {P} B}$

Редукции Тьюринга

Сведение по Тьюрингу за полиномиальное время от проблемы A к проблеме B - это алгоритм, который решает проблему A, используя полиномиальное количество вызовов подпрограммы для проблемы B и полиномиальное время вне этих вызовов подпрограмм. Редукции Тьюринга за полиномиальное время также известны как редукции Кука , названные в честь Стивена Кука . Редукцию этого типа можно обозначить выражением . Сокращения на несколько единиц можно рассматривать как ограниченные варианты сокращений Тьюринга, где количество вызовов, сделанных для подпрограммы для задачи B, равно единице, а значение, возвращаемое сокращением, является тем же значением, что и значение, возвращаемое подпрограммой. ${\ Displaystyle A \ leq _ {T} ^ {P} B}$

Полнота

Полная задача для данной сложности класса C и сокращения ≤ является проблемой Р , которая принадлежит C , таким образом, что каждая задача в C имеет уменьшение ≤ P . Например, задача является NP- полной, если она принадлежит NP и все задачи в NP имеют много-единичные редукции за полиномиальное время. Задача, принадлежащая NP, может быть доказана как NP- полная путем нахождения единственной полиномиальной редукции много-единицы к ней из известной NP- полной задачи. Полиномиальные многоместные одно сокращение, были использованы для определения полных задач для других классов сложности, в том числе PSPACE -полных языков и EXPTIME -полных языков.

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

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

Определения классов сложности NP , PSPACE и EXPTIME не предполагают редукций: редукции входят в их изучение только при определении полных языков для этих классов. Однако в некоторых случаях класс сложности может быть определен сокращениями. Если C - любая проблема решения , то можно определить класс сложности C, состоящий из языков A, для которых . В этом случае C будет автоматически завершен для C , но у C могут быть и другие полные проблемы. ${\ Displaystyle A \ leq _ {m} ^ {P} C}$

Примером этого является класс сложности, определенный из экзистенциальной теории вещественных чисел , вычислительная проблема, которая известна как NP- трудная и в PSPACE , но не известна как полная для NP , PSPACE или любого языка в полиноме. иерархия . представляет собой набор задач, имеющих полиномиальное время много-однозначной редукции к экзистенциальной теории вещественных чисел; он имеет несколько других полных задач , таких как определение прямолинейного числа пересечений в качестве неориентированного графа . Каждая проблема наследует свойство принадлежности к PSPACE , и каждая завершенная проблема является NP- сложной. ${\ Displaystyle \ существует \ mathbb {R}}$${\ Displaystyle \ существует \ mathbb {R}}$${\ Displaystyle \ существует \ mathbb {R}}$${\ Displaystyle \ существует \ mathbb {R}}$

Точно так же класс сложности GI состоит из задач, которые могут быть сведены к проблеме изоморфизма графов . Поскольку известно, что изоморфизм графов принадлежит как NP, так и co- AM , то же самое верно для каждой задачи в этом классе. Проблема GI -полная, если она полная для этого класса; сама проблема изоморфизма графов является GI -полной, как и несколько других связанных проблем.

Смотрите также

• 21 NP-полная задача Карпа

внешние ссылки

• MIT OpenCourseWare: 16. Сложность: P, NP, NP-полнота, редукции

использованная литература