Задачи #P-complete (произносится как «sharp P complete» или «number P complete») образуют класс сложности в теории вычислительной сложности . Задачи в этом классе сложности определяются следующими двумя свойствами:
#P-полные задачи по крайней мере так же сложны, как и NP-полные задачи. [1] Полиномиальный алгоритм решения #P-полной задачи, если бы он существовал, решил бы задачу P против NP , подразумевая, что P и NP равны. Такой алгоритм неизвестен, как и доказательство того, что такого алгоритма не существует.
Примеры #P-полных задач включают в себя:
Все они обязательно являются членами класса #P . В качестве не-примера рассмотрим случай подсчета решений проблемы 1-выполнимости: ряд переменных, каждая из которых по отдельности ограничена, но не имеет связей друг с другом. Решения можно эффективно подсчитать, умножив количество вариантов для каждой переменной в изоляции. Таким образом, эта задача находится в #P , но не может быть #P-полной, если только #P = FP . Это было бы удивительно, так как это означало бы, что P = NP = PH .
Некоторые #P-полные задачи соответствуют легким ( полиномиальным по времени ) задачам. Определить выполнимость булевой формулы в DNF легко: такая формула выполнима тогда и только тогда, когда она содержит выполнимую конъюнкцию (ту, которая не содержит переменную и ее отрицание), тогда как подсчет количества удовлетворяющих присваиваний является #P-полным. Более того, определение 2-выполнимости легко по сравнению с подсчетом количества удовлетворяющих присваиваний. Топологическая сортировка проста в отличие от подсчета количества топологических сортировок. Одно совершенное паросочетание можно найти за полиномиальное время, но подсчет всех совершенных паросочетаний является #P-полным. Задача подсчета совершенного паросочетания была первой задачей подсчета, соответствующей легкой задаче P, которая, как было показано, является #P-полной в статье 1979 года Лесли Валианта , где также впервые были определены класс #P и задачи #P-полные. [3]
Существуют вероятностные алгоритмы , которые возвращают хорошие приближения к некоторым #P-полным проблемам с высокой вероятностью. Это одна из демонстраций силы вероятностных алгоритмов.
Многие #P-полные задачи имеют полностью полиномиальную по времени рандомизированную схему аппроксимации , или «FPRAS», которая, неформально, будет производить с высокой вероятностью аппроксимацию с произвольной степенью точности, за время, которое является полиномиальным относительно как размера задачи, так и степени требуемой точности. Джеррум , Валиант и Вазирани показали, что каждая #P-полная задача либо имеет FPRAS, либо ее по существу невозможно аппроксимировать; если существует какой-либо полиномиальный по времени алгоритм, который последовательно производит аппроксимацию #P-полной задачи, которая находится в пределах полиномиального отношения к размеру ввода точного ответа, то этот алгоритм может быть использован для построения FPRAS. [4]