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

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

В теории вычислительной сложности и игровой сложности экономное сокращение — это преобразование от одной задачи к другой ( сокращение ), которое сохраняет количество решений. Неформально, это биекция между соответствующими наборами решений двух задач. Общее сокращение от задачи к задаче — это преобразование, которое гарантирует, что всякий раз, когда есть решение, также есть по крайней мере одно решение и наоборот. Экономное сокращение гарантирует, что для каждого решения существует единственное решение и наоборот. ${\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 - CNF . Любое допустимое присваивание булевой формулы является допустимым присваиванием соответствующей формулы 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-полной.

Шакашака

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

Ссылки

1. Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, 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 Texts in Theoretical Computer Science, Springer, стр. 363, ISBN 9783540299530
4. Гомес, Карла П.; Сабхарвал, Ашиш; Селман, Барт (2009), «Глава 20. Подсчет моделей», в Biere, Armin; Heule, Marijn ; van Maaren, Hans; Walsh, Toby (ред.), Handbook of Satisfiability (PDF) , Frontiers in Artificial Intelligence and Applications, т. 185, IOS Press, стр. 633–654, ISBN 9781586039295. См. в частности стр. 634–635.
5. Лихтенштейн, Дэвид (май 1982 г.). «Планарные формулы и их использование». Журнал SIAM по вычислениям . 11 (2): 329–343. doi :10.1137/0211025. ISSN  0097-5397.
6. Сета, Такахиро (2001). Сложности головоломок, перекрестная сумма и другие проблемы их решения (ASP) . CiteSeerX 10.1.1.81.7891 . 
7. "Репозиторий JAIST: Вычислительная сложность и модель целочисленного программирования Шакашака". dspace.jaist.ac.jp . Получено 15.05.2019 .