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

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

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

Типы скидок [ править ]

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

Сокращения на несколько единиц [ править ]

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

Сокращения таблицы истинности [ править ]

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

Редукции Тьюринга [ править ]

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

Полнота [ править ]

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

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

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

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

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

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

См. Также [ править ]

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

Внешние ссылки [ править ]

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

Ссылки [ править ]

^ a b c Клейнберг, Джон; Тардос, Ива Тардос (2006). Разработка алгоритмов . Pearson Education. С. 452–453. ISBN 978-0-321-37291-8.
^ Вегенер, Инго (2005), Теория сложности: изучение пределов эффективных алгоритмов , Springer, стр. 60, ISBN 9783540274773.
^ Мандал, Дебасис; Паван, А .; Венугопалан, Раджешвари (2014). Отделение полноты Кука от полноты Карпа-Левина в рамках гипотезы жесткости наихудшего случая . 34-я Международная конференция по основам программных технологий и теоретической информатики. ISBN 978-3-939897-77-4.
^ a b Голдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 59–60, ISBN 9781139472746
^ Басс, SR ; Хей, Л. (1988), «Об истинности таблицы сводимости к SAT и разностной иерархии над НП», Труды Третьей Ежегодной структуры сложности Теория конференции , С. 224-233,. CiteSeerX 10.1.1.5.2387 , DOI : 10,1109 /SCT.1988.5282 , ISBN 978-0-8186-0866-7.
^ Гарей, Майкл Р .; Джонсон, Д.С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman.
↑ Aho, AV (2011), «Теория сложности», в Blum, EK; Ахо А.В. (ред.), Computer Science: Аппаратные средства, программное обеспечение и его сердце ., С. 241-267, DOI : 10.1007 / 978-1-4614-1168-0_12 , ISBN 978-1-4614-1167-3. См., В частности, стр. 255.
^ Гринлоу, Раймонд; Гувер, Джеймс; Руццо, Уолтер (1995), Пределы параллельных вычислений; Теория П-полноты , ISBN 978-0-19-508591-4. В частности, аргумент о том, что каждая нетривиальная задача в P имеет полиномиальное преобразование многих единиц к любой другой нетривиальной задаче, см. На стр. 48.
^ Шефер, Маркус (2010), «Сложность некоторых геометрических и топологических задач» (PDF) , Graph Drawing, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Revised Papers , Lecture Notes in Computer Science, 5849 ., Springer-Verlag, стр 334-344, DOI : 10.1007 / 978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
^ Кёблер, Йоханнес; Шёнинг, Уве ; Торан, Якобо (1993), Проблема изоморфизма графов: ее структурная сложность , Биркхойзер, ISBN 978-0-8176-3680-7, OCLC 246882287.

[kleinberg-tardos-1] Клейнберг, Джон; Тардос, Ива Тардос (2006). Разработка алгоритмов . Pearson Education. С. 452–453. ISBN 978-0-321-37291-8.

[2] Вегенер, Инго (2005), Теория сложности: изучение пределов эффективных алгоритмов , Springer, стр. 60, ISBN 9783540274773.

[mandal2014-3] Мандал, Дебасис; Паван, А .; Венугопалан, Раджешвари (2014). Отделение полноты Кука от полноты Карпа-Левина в рамках гипотезы жесткости наихудшего случая . 34-я Международная конференция по основам программных технологий и теоретической информатики. ISBN 978-3-939897-77-4.

[goldreich-4] Голдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 59–60, ISBN 9781139472746

[5] Басс, SR ; Хей, Л. (1988), «Об истинности таблицы сводимости к SAT и разностной иерархии над НП», Труды Третьей Ежегодной структуры сложности Теория конференции , С. 224-233,. CiteSeerX 10.1.1.5.2387 , DOI : 10,1109 /SCT.1988.5282 , ISBN 978-0-8186-0866-7.

[6] Гарей, Майкл Р .; Джонсон, Д.С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman.

[7] Aho, AV (2011), «Теория сложности», в Blum, EK; Ахо А.В. (ред.), Computer Science: Аппаратные средства, программное обеспечение и его сердце ., С. 241-267, DOI : 10.1007 / 978-1-4614-1168-0_12 , ISBN 978-1-4614-1167-3. См., В частности, стр. 255.

[8] Гринлоу, Раймонд; Гувер, Джеймс; Руццо, Уолтер (1995), Пределы параллельных вычислений; Теория П-полноты , ISBN 978-0-19-508591-4. В частности, аргумент о том, что каждая нетривиальная задача в P имеет полиномиальное преобразование многих единиц к любой другой нетривиальной задаче, см. На стр. 48.

[9] Шефер, Маркус (2010), «Сложность некоторых геометрических и топологических задач» (PDF) , Graph Drawing, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Revised Papers , Lecture Notes in Computer Science, 5849 ., Springer-Verlag, стр 334-344, DOI : 10.1007 / 978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.

[10] Кёблер, Йоханнес; Шёнинг, Уве ; Торан, Якобо (1993), Проблема изоморфизма графов: ее структурная сложность , Биркхойзер, ISBN 978-0-8176-3680-7, OCLC 246882287.

[1]