Экономное сокращение - Parsimonious reduction

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

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

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

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

Приложения

Подобно тому , как много-одно сокращения имеет важное значение для доказательства NP-полноты , экономные сокращения имеют важное значение для доказательства полноты для подсчета классов сложности , таких как ♯P . Поскольку экономные сокращения сохраняют свойство иметь уникальное решение, они также используются в сложности игры , чтобы показать сложность головоломок, таких как судоку, где уникальность решения является важной частью определения головоломки.

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

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

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

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

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

# 3СБ

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

Планар №3САТ

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

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

Счетная версия этой задачи запрашивает количество гамильтоновых циклов в данном ориентированном графе . Seta Takahiro обеспечил сокращение этой проблемы с 3SAT при ограничении планарными ориентированными графами максимальной степени-3. Редукция обеспечивает взаимно однозначное соответствие между решениями экземпляра 3SAT и решениями экземпляра гамильтонова цикла в плоских ориентированных графах максимальной степени-3. Следовательно, редукция является экономной, и гамильтонов цикл в плоских ориентированных графах максимальной степени 3 является # P-полным. Следовательно, общая версия проблемы гамильтонова цикла также должна быть # P-полной.

Шакашака

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

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