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

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

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

Виды скидок

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

Сокращение «много-один»

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

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

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

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

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

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

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

См. также

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с Кляйнберг, Джон ; Тардос, Ева (2006). Алгоритм проектирования . Пирсон Образование. стр. 452–453. ISBN 978-0-321-37291-8 .
^ Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов , Springer, стр. 60, ISBN 9783540274773 .
^ Мандал, Дебасис; Паван, А.; Венугопалан, Раджешвари (2014). Отделение полноты Кука от полноты Карпа-Левина при наихудшей гипотезе твердости . 34-я Международная конференция по основам программных технологий и теоретической информатики. ISBN 978-3-939897-77-4 .
^ Jump up to: ^а ^б Гольдрейх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 59–60, ISBN 9781139472746
^ Бусс, СР ; Хэй, Л. (1988), «О сводимости таблицы истинности к SAT и разностной иерархии над NP», Труды третьей ежегодной конференции по теории структуры сложности , стр. 224–233, CiteSeerX 10.1.1.5.2387 , doi : 10.1109 /SCT.1988.5282 , ISBN 978-0-8186-0866-7 .
^ Гэри, Майкл Р .; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman .
^ Ахо, А.В. (2011), «Теория сложности», в Блюме, Е.К.; Ахо, А.В. (ред.), Информатика: аппаратное обеспечение, программное обеспечение и суть этого , стр. 241–267, doi : 10.1007/978-1-4614-1168-0_12 , ISBN 978-1-4614-1167-3 . См., в частности, стр. 255.
^ Гринлоу, Раймонд; Гувер, Джеймс; Руццо, Уолтер (1995), Пределы параллельных вычислений; Теория P-полноты , ISBN 978-0-19-508591-4 . В частности, аргумент о том, что каждая нетривиальная проблема в P имеет полиномиальное сведение «много-единица» к любой другой нетривиальной задаче, см. в p. 48.
^ Шефер, Маркус (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 .
^ Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: ее структурная сложность , Биркхойзер, ISBN 978-0-8176-3680-7 , OCLC 246882287 .

[kleinberg-tardos-1] Jump up to: ^а ^б ^с Кляйнберг, Джон ; Тардос, Ева (2006). Алгоритм проектирования . Пирсон Образование. стр. 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] Jump up to: ^а ^б Гольдрейх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 59–60, ISBN 9781139472746

[5] Бусс, СР ; Хэй, Л. (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), «Теория сложности», в Блюме, Е.К.; Ахо, А.В. (ред.), Информатика: аппаратное обеспечение, программное обеспечение и суть этого , стр. 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 имеет полиномиальное сведение «много-единица» к любой другой нетривиальной задаче, см. в 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]