Экономное сокращение

Понятие в теории сложности вычислений.

В теории сложности вычислений и сложности игр экономное сокращение — это преобразование одной задачи в другую ( сокращение ), сохраняющее количество решений. Неформально это биекция между соответствующими множествами решений двух задач. Общая редукция от проблемы к проблеме — это преобразование, гарантирующее, что всякий раз, когда существует решение, также есть хотя бы одно решение, и наоборот. Экономное сокращение гарантирует, что для каждого решения существует единственное решение и наоборот. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Экономные сокращения обычно используются в вычислительной сложности для доказательства сложности задач подсчета , для подсчета классов сложности, таких как #P . Кроме того, они используются для повышения сложности игры как способ создания сложных головоломок, имеющих уникальное решение, как того требуют многие типы головоломок.

Формальное определение

Пусть это будет пример проблемы . Экономное сокращение от проблемы к проблеме — это такое сокращение, при котором количество решений равно числу решений проблемы . ^[1] Если такое сокращение существует, и если у нас есть оракул, который подсчитывает количество решений, для которого является экземпляром , то мы можем разработать алгоритм, который подсчитывает количество решений для , соответствующего экземпляра . Следовательно, если подсчитать количество решений для экземпляров сложно, то подсчитать количество решений для также должно быть сложно. ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle R(x)}$ ${\displaystyle R(x)}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$

Приложения

Точно так же, как сокращения «многие единицы» важны для доказательства NP-полноты , экономные сокращения важны для доказательства полноты для подсчета классов сложности , таких как #P . ^[1] Поскольку экономные сокращения сохраняют свойство иметь уникальное решение, они также используются в играх на сложность , чтобы показать сложность головоломок, таких как судоку , где уникальность решения является важной частью определения головоломки. ^[2]

Конкретные типы экономных сокращений могут определяться вычислительной сложностью или другими свойствами алгоритма преобразования. Например, экономное сокращение за полиномиальное время — это такое, при котором алгоритм преобразования занимает полиномиальное время . Это типы редукции, используемые для доказательства #P-полноты . ^[1] В параметризованной сложности используются экономные сокращения FPT ; это экономные сокращения, преобразование которых представляет собой управляемый алгоритм с фиксированными параметрами и которые отображают ограниченные значения параметров в ограниченные значения параметров с помощью вычислимой функции. ^[3]

Экономные сокращения за полиномиальное время являются частным случаем более общего класса сокращений для задач счета, сокращений счета за полиномиальное время . ^[4]

Один из распространенных методов, используемых для доказательства экономичности редукции, состоит в том, чтобы показать, что существует биекция между набором решений и набором решений, гарантирующим, что количество решений обеих задач одинаково. ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle R(x)}$

Примеры экономного сокращения при доказательстве #P-полноты

Класс #P содержит счетные версии задач решения NP. Учитывая пример проблемы решения NP, проблема требует количества решений проблемы. Примеры #P-полноты, приведенные ниже, основаны на том факте, что #SAT является #P-полнотой. ${\displaystyle x}$ ${\displaystyle X,}$ ${\displaystyle \#x}$ ${\displaystyle x.}$

#3САТ

Это счетная версия 3SAT . Можно показать, что любую булеву формулу можно переписать в виде формулы в форме 3- КНФ . Любое допустимое присвоение логической формулы является допустимым присвоением соответствующей формулы 3-CNF, и наоборот. Следовательно, это сокращение сохраняет количество удовлетворяющих назначений и является экономным сокращением. Тогда #SAT и #3SAT являются счетными эквивалентами, а #3SAT также #P-полным.

Планар #3SAT

Это счетная версия Planar 3SAT. Снижение жесткости от 3SAT до Planar 3SAT, данное Лихтенштейном ^[5], имеет дополнительное свойство, заключающееся в том, что для каждого допустимого назначения экземпляра 3SAT существует уникальное допустимое присвоение соответствующего экземпляра Planar 3SAT, и наоборот. Следовательно, редукция является экономной, и, следовательно, Planar #3SAT является #P-полной.

Гамильтонов цикл

Версия этой задачи со счетом требует узнать количество гамильтоновых циклов в заданном ориентированном графе . ^{Сета Такахиро предложил [6]} сокращение 3SAT к этой проблеме, ограничиваясь планарными ориентированными графами максимальной степени 3. Сокращение обеспечивает биекцию между решениями экземпляра 3SAT и решениями экземпляра гамильтонова цикла в плоских направленных графах максимальной степени 3. Следовательно, редукция является экономной, а гамильтонов цикл в плоских ориентированных графах максимальной степени 3 является #P-полным. Следовательно, общая версия проблемы гамильтонова цикла также должна быть #P-полной.

Шакашака

Шакашака — пример того, как экономное сокращение можно использовать для демонстрации сложности логических головоломок. Версия решения этой проблемы спрашивает, существует ли решение для данного экземпляра головоломки. Версия подсчета требует количества различных решений такой проблемы. Сокращение Planar 3SAT, данное Деменом, Окамото, Уэхарой ​​и Уно ^[7], также обеспечивает биекцию между набором решений экземпляра Planar 3SAT и набором решений соответствующего экземпляра Shakashaka. Следовательно, сокращение является экономным, а счетная версия Шакашаки является #P-полной.

Рекомендации

1. Голдрейх, Одед (2008), Вычислительная сложность: концептуальная перспектива, Cambridge University Press, стр. 203–204, ISBN 9781139472746
2. Ято, Такаюки; Сета, Такахиро (2003), «Сложность и полнота поиска другого решения и его применение к головоломкам», IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , E86-A (5): 1052–1060
3. Флам, Дж.; Гроэ, М. (2006), Параметризованная теория сложности, Тексты EATCS по теоретической информатике, Springer, стр. 363, ISBN 9783540299530
4. Гомес, Карла П .; Сабхарвал, Ашиш; Селман, Барт (2009), «Глава 20. Подсчет моделей», в Бьере, Армин; Heule, Марин ; ван Маарен, Ганс; Уолш, Тоби (ред.), Справочник по выполнимости (PDF) , «Границы искусственного интеллекта и приложений», том. 185, IOS Press, стр. 633–654, ISBN. 9781586039295. См., в частности, стр. 634–635.
5. Лихтенштейн, Дэвид (май 1982 г.). «Плоские формулы и их использование». SIAM Journal по вычислительной технике . 11 (2): 329–343. дои : 10.1137/0211025. ISSN  0097-5397.
6. Сета, Такахиро (2001). Сложности головоломок, перекрестная сумма и задачи другого их решения (ASP) . CiteSeerX 10.1.1.81.7891 . 
7. «Репозиторий JAIST: вычислительная сложность и модель целочисленного программирования Шакашаки» . dspace.jaist.ac.jp . Проверено 15 мая 2019 г.