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

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

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

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

Позволять ${ displaystyle x}$ быть примером проблемы ${ displaystyle X}$ . А Экономное сокращение ${ displaystyle R}$ от проблемы ${ displaystyle X}$ к проблеме ${ displaystyle Y}$ такое сокращение, что количество решений ${ displaystyle x}$ равно количеству решений проблемы ${ Displaystyle R (х)}$ .^[1] Если такое сокращение существует, и если у нас есть оракул, который считает количество решений ${ Displaystyle R (х)}$ который является примером ${ 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 (х)}$ что гарантирует, что количество решений обеих проблем одинаково.

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

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

# 3СБ

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

Планар №3САТ

Это счетная версия 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-полной.