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

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

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

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

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

Приложения

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

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

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

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

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

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

#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-полной.

Ссылки

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

[goldreich-1] Jump up to: ^а ^б ^с Гольдрайх, Одед (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 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]