Сокращение за полиномиальное время

Метод решения одной проблемы с помощью другой

В теории вычислительной сложности полиномиальное сокращение — это метод решения одной проблемы с помощью другой. Он показывает, что если существует гипотетическая подпрограмма, решающая вторую проблему, то первую проблему можно решить, преобразовав или сократив ее до входных данных для второй проблемы и вызвав подпрограмму один или несколько раз. Если и время, необходимое для преобразования первой проблемы во вторую, и количество вызовов подпрограммы, являются полиномиальными , то первая проблема полиномиально сводится ко второй. ^[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] ${\displaystyle A\leq _{tt}^{P}B}$

Сокращение Тьюринга

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

Полнота

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Кляйнберг, Джон ; Тардос, Ева (2006). Алгоритм проектирования . Пирсон Образование. стр. 452–453. ISBN 978-0-321-37291-8.
2. Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов , Springer, стр. 60, ISBN 9783540274773.
3. Мандал, Дебасис; Паван, А.; Венугопалан, Раджешвари (2014). Разделение полноты Кука от полноты Карпа-Левина в соответствии с гипотезой о наихудшем случае. 34-я Международная конференция по основам технологий программного обеспечения и теоретической информатики. ISBN 978-3-939897-77-4.
4. Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press, стр. 59–60, ISBN 9781139472746
5. Басс, SR ; Хей, Л. (1988), «О сводимости таблицы истинности к SAT и иерархии различий над NP», Труды Третьей ежегодной конференции по теории сложности , стр. 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. Ахо, А. В. (2011), «Теория сложности», в Blum, EK; Ахо, А. В. (ред.), Computer Science: The Hardware, Software and Heart of It , стр. 241–267, doi : 10.1007/978-1-4614-1168-0_12 , ISBN 978-1-4614-1167-3. См. в частности стр. 255.
8. Гринлоу, Рэймонд; Гувер, Джеймс; Руццо, Уолтер (1995), Пределы параллельных вычислений; Теория P-полноты , ISBN 978-0-19-508591-4. В частности, аргумент о том, что каждая нетривиальная задача в P имеет полиномиальное сведение к любой другой нетривиальной задаче с помощью метода многих единиц, см. на стр. 48.
9. Шефер, Маркус (2010), «Сложность некоторых геометрических и топологических проблем» (PDF) , Рисование графов, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Пересмотренные статьи , Заметки лекций по информатике, т. 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.