Уменьшение счета за полиномиальное время

В теории сложности вычислений в счетных задачах , уменьшение счета за полиномиальное время является тип редукции (преобразование от одной задачи к другому) используется для определения понятия полноты для класса сложности ♯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}$

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

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

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

Приложения в теории сложности [ править ]

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

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

Ссылки [ править ]