Уменьшение счета за полиномиальное время - Polynomial-time counting reduction

в теория сложности вычислений из проблемы с подсчетом, а уменьшение счета за полиномиальное время это тип снижение (переход от одной проблемы к другой) используется для определения понятия полнота для класса сложности ♯P.^[1] Эти сокращения также можно назвать полиномиальные редукции с подсчетом многих единиц или же слабо экономные сокращения; они аналогичны много-одно сокращение за проблемы решения и они обобщают экономные скидки.^[2]

Определение

Сокращение счета за полиномиальное время обычно используется для преобразования экземпляров известной трудной задачи. ${ displaystyle X}$ в примеры другой проблемы ${ displaystyle Y}$ это должно быть трудно доказать. Он состоит из двух функций ${ displaystyle f}$ и ${ displaystyle g}$, оба из которых должны быть вычислимы в полиномиальное время. Функция ${ displaystyle f}$ преобразует входные данные для ${ displaystyle X}$ во входы для ${ displaystyle Y}$, а функция ${ displaystyle g}$ преобразует выходы для ${ displaystyle Y}$ в выходы для ${ displaystyle X}$.^[1][2]

Эти две функции должны сохранять правильность вывода. То есть предположим, что преобразование ввода ${ displaystyle x}$ для проблемы ${ displaystyle X}$ к входу ${ Displaystyle у = е (х)}$ для проблемы ${ displaystyle Y}$, а затем решается ${ displaystyle y}$ производить продукцию ${ displaystyle z}$. Должно быть так, что преобразованный вывод ${ displaystyle g (z)}$ правильный вывод для исходного ввода ${ displaystyle x}$. То есть, если отношения ввода-вывода ${ displaystyle X}$ и ${ displaystyle Y}$ выражаются как функции, то их функциональная композиция должен подчиняться личность ${ Displaystyle X = г circ Y circ f}$. В качестве альтернативы можно выразить через алгоритмы, один из возможных алгоритмов решения ${ displaystyle X}$ было бы применить ${ displaystyle f}$ превратить проблему в пример ${ displaystyle Y}$, решите этот экземпляр, а затем примените ${ displaystyle g}$ преобразовать вывод ${ displaystyle Y}$ в правильный ответ для ${ displaystyle X}$.^[1][2]

Отношение к другим видам редукции

В частном случае экономное сокращение является полиномиальным преобразованием ${ displaystyle f}$ на входах к задачам, который сохраняет точные значения выходов. Такое сокращение можно рассматривать как сокращение счета за полиномиальное время, используя функция идентичности как функция ${ displaystyle g}$.^[1][2]

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

Функциональная проблема (заданная входами и желаемыми выходами) относится к классу сложности ♯P если существует недетерминированная машина Тьюринга который выполняется за полиномиальное время, для которого выходом задачи является количество принимающих путей машины Тьюринга. Интуитивно такие задачи подсчитывают количество решений задач в классе сложности. НП. Функциональная проблема ${ displaystyle Y}$ называется ♯P-трудным, если существует полиномиальная считающая редукция из каждой задачи ${ displaystyle X}$ в ♯P до ${ displaystyle Y}$. Если, кроме того, ${ displaystyle Y}$ сам принадлежит ♯P, то ${ displaystyle Y}$ как говорят ♯P-полный.^[1][2] (Иногда, как в оригинальной статье Valiant доказательство полноты перманента матриц 0–1, более слабое понятие редукции, Редукция Тьюринга, вместо этого используется для определения ♯P-полноты.^[3])

Обычный метод доказательства проблемы ${ displaystyle Y}$ в ♯P быть P-полным - значит начинать с одной известной проблемы P-полной ${ displaystyle X}$ и найти сокращение счета за полиномиальное время из ${ displaystyle X}$ к ${ displaystyle Y}$. Если эта редукция существует, то существует редукция любой другой задачи в ♯P к ${ displaystyle Y}$, полученный составление сокращение от другой проблемы до ${ displaystyle X}$ с сокращением от ${ displaystyle X}$ к ${ displaystyle Y}$.^[1][2]

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