Сокращение счета за полиномиальное время

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

Сокращение подсчета за полиномиальное время обычно используется для преобразования примеров известной сложной проблемы в примеры другой проблемы , сложность которой должна быть доказана. Оно состоит из двух функций и , обе из которых должны быть вычислимы за полиномиальное время . Функция преобразует входные данные для во входные данные для , а функция преобразует выходные данные для в выходные данные для . ^{[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 y=f(x)}$${\displaystyle Y}$${\displaystyle y}$${\displaystyle z}$${\displaystyle g(z)}$${\displaystyle x}$${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle X=g\circ Y\circ f}$${\displaystyle X}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle g}$${\displaystyle Y}$${\displaystyle X}$

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

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

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