Введение
Класс сложности #P-полные задачи (произносится "шарп P-полные" или "число P-полные") образует класс сложности в теории вычислительной сложности. Задачи в этом классе сложности определяются двумя свойствами: задача принадлежит классу #P, который состоит из задач, определяемых как подсчет числа допустимых путей недетерминированной машины Тьюринга, работающей за полиномиальное время. Задача является #P-трудной, что означает, что любая другая задача из #P имеет полиномиальное время сведения Тьюринга или сведения подсчетом к ней. Сведение подсчетом – это пара полиномиальных преобразований: из входных данных другой задачи в входные данные данной задачи и из выходных данных данной задачи в выходные данные другой задачи, позволяющее решить другую задачу, используя любой подпрограммный модуль для данной задачи. Сведение Тьюринга – это алгоритм для другой задачи, который делает полиномиальное число вызовов подпрограммного модуля для данной задачи и, помимо этих вызовов, использует полиномиальное время. В некоторых случаях используются экономные сведения – более специфичный тип сведения, сохраняющий точное количество решений. #P-полные задачи не проще, чем NP-полные задачи. Алгоритм, решающий #P-полную задачу за полиномиальное время (если бы он существовал), решил бы проблему P против NP, подразумевая, что P = NP. Такого алгоритма не известно, и доказательства его несуществования также не известны.
The #P complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties:
The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial time non deterministic Turing machine. The problem is #P hard, meaning that every other problem in #P has a Turing reduction or polynomial time counting reduction to it. A counting reduction is a pair of polynomial time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial time. In some cases parsimonious reductions, a more specific type of reduction that preserves the exact number of solutions, are used. #P complete problems are at least as hard as NP complete problems. A polynomial time algorithm for solving a #P complete problem, if it existed, would solve the P versus NP problem by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist.
Легкие проблемы с версиями с жестким подсчетом
Некоторые #P-полные задачи соответствуют простым (вычислимым за полиномиальное время) задачам. Определение выполнимости булевой формулы в ДНФ легко: такая формула выполнима тогда и только тогда, когда она содержит выполнимую конъюнкцию (не содержащую переменную и её отрицание). В то же время, подсчёт количества выполнимых назначений является #P-полной задачей. Более того, определение 2-выполнимости проще, чем подсчёт количества выполнимых назначений. Топологическая сортировка проста, в отличие от подсчёта количества топологических сортировок. Единственное совершенное паросочетание можно найти за полиномиальное время, но подсчёт всех совершенных паросочетаний является #P-полной задачей. Задача подсчёта совершенных паросочетаний была первой задачей подсчёта, соответствующей простой задаче P, показанной как #P-полная, в статье Лесли Валианта 1979 года, в которой также впервые были определены класс #P и #P-полные задачи.
Приближение
Существуют вероятностные алгоритмы, которые с высокой вероятностью возвращают хорошие приближения для некоторых #P-полных задач. Это одна из демонстраций возможностей вероятностных алгоритмов. Для многих #P-полных задач существует полностью полиномиальная схема рандомизированного приближения во времени, или "FPRAS", которая, по сути, с высокой вероятностью выдает приближение с заданной степенью точности за время, полиномиальное как относительно размера задачи, так и относительно требуемой степени точности. Jerrum, Valiant и Vazirani показали, что каждая #P-полная задача либо имеет FPRAS, либо принципиально не поддается приближению; если существует полиномиальный алгоритм, который последовательно находит приближение #P-полной задачи, отличающееся от точного решения на величину, полиномиальную относительно размера входных данных, то этот алгоритм можно использовать для построения FPRAS.