Полиномиальное сокращение

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

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

• 1 Типы сокращений
  • 1.1 Сокращения на несколько единиц
  • 1.2 Сокращения по таблице истинности
  • 1.3 Редукции по Тьюрингу
• 2 Полнота
• 3 Определение классов сложности
• 4 См. также
• 5 Внешние ссылки
• 6 Ссылки

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

редукции по многим единицам

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

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

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

редукции по Тьюрингу

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

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

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

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

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

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

• 21 NP-полная проблема Карпа

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