♯P-полный - ♯P-complete

Правильный заголовок этой статьи: # P-complete. Замена # связано с технические ограничения.

В # P-complete задачи (произносится как «диез P завершено» или «число P завершено») образуют класс сложности в теория сложности вычислений. Проблемы этого класса сложности определяются двумя следующими свойствами:

  • Проблема в #П, класс задач, который можно определить как подсчет количества принимающих путей полиномиальное время недетерминированная машина Тьюринга.
  • Проблема в #П -жестко, что означает, что у любой другой проблемы в #P есть Редукция Тьюринга или же уменьшение счета за полиномиальное время к нему. Сокращение счета - это пара полиномиальных преобразований от входов другой задачи к входам данной задачи и от выходов данной задачи к выходам другой задачи, позволяющих решить другую задачу с использованием любой подпрограммы для данной задачи. проблема. Редукция по Тьюрингу - это алгоритм для другой задачи, который делает полиномиальное количество вызовов подпрограммы для данной проблемы и, помимо этих вызовов, использует полиномиальное время. В некоторых случаях экономные скидки, используется более конкретный тип редукции, сохраняющий точное количество решений.

Алгоритм с полиномиальным временем для решения # P-полной задачи, если бы он существовал, решил бы P против проблемы NP подразумевая, что P и NP равны. Такой алгоритм не известен, и не известно доказательств того, что такой алгоритм не существует.

Примеры

Примеры проблем # P-complete:

Все это обязательно члены класса #П также. В качестве не примера рассмотрим случай подсчета решений 1-выполнимость проблема: ряд переменных, каждая из которых ограничена индивидуально, но не связана друг с другом. Решения можно эффективно подсчитать, умножив количество вариантов отдельно для каждой переменной. Таким образом, эта проблема находится в #П, но не может быть # P-полным, если #П =FP. Это было бы удивительно, поскольку это означало бы, что п =НП =PH.

Простые проблемы с жестким подсчетом версий

Некоторые # P-полные задачи соответствуют легким (полиномиальное время ) проблемы. Определить выполнимость булевой формулы в DNF легко: такая формула выполнима тогда и только тогда, когда она содержит выполнимую конъюнкцию (ту, которая не содержит переменную и ее отрицание), тогда как подсчет количества удовлетворяющих присваиваний равен # P- полный. Кроме того, решение о 2-выполнимости легко по сравнению с подсчетом количества выполнимых заданий. Топологическая сортировка легко в отличие от подсчета количества топологических сортировок. Один идеальное соответствие может быть найден за полиномиальное время, но подсчет всех точных совпадений является # P-полным. Идеальная задача подсчета совпадений была первой задачей подсчета, соответствующей простой P-задаче, которая была # P-полной в статье 1979 г. Лесли Валиант которые также впервые определили класс #P и проблемы #P-complete.[2]

Приближение

Есть вероятностные алгоритмы которые с высокой вероятностью возвращают хорошие приближения к некоторым # P-полным задачам. Это одна из демонстраций силы вероятностных алгоритмов.

Многие проблемы # P-complete имеют полностью полиномиальная схема рандомизированной аппроксимации, или «FPRAS», который, неофициально, с высокой вероятностью даст приближение с произвольной степенью точности по времени, полиномиальному как по размеру проблемы, так и по степени требуемой точности. Jerrum, Доблестный, и Вазирани показал, что каждая # P-полная задача либо имеет FPRAS, либо ее невозможно аппроксимировать; если существует какой-либо алгоритм с полиномиальным временем, который последовательно производит аппроксимацию # P-полной задачи, которая находится в пределах полиномиального отношения размера входных данных точного ответа, то этот алгоритм можно использовать для построения FPRAS.[3]

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

  1. ^ Brightwell, Graham R .; Винклер, Питер (1991). «Подсчет линейных расширений». Заказ. 8 (3): 225–242. Дои:10.1007 / BF00383444..
  2. ^ Лесли Г. Валиант (1979). «Сложность вычисления постоянного». Теоретическая информатика. Эльзевир. 8 (2): 189–201. Дои:10.1016/0304-3975(79)90044-6.
  3. ^ Марк Р. Джеррам; Лесли Г. Валиант; Виджай В. Вазирани (1986). «Случайная генерация комбинаторных структур из равномерного распределения». Теоретическая информатика. Эльзевир. 43: 169–188. Дои:10.1016 / 0304-3975 (86) 90174-х.

дальнейшее чтение

  • Вазирани, Виджай В. (2003). Алгоритмы аппроксимации. Берлин: Springer. ISBN  3-540-65367-8.