♯P-полный
# P -полные задачи (произносится как «острый P-полный» или «число P-полный») образуют класс сложности в теории сложности вычислений . Проблемы этого класса сложности определяются наличием следующих двух свойств:
- Проблема заключается в #P , классе проблем, которые можно определить как подсчет количества принимающих путей с полиномиальным временем недетерминированной машины Тьюринга .
- Проблема #P -трудна, что означает, что каждая другая проблема в #P имеет сокращение Тьюринга или сокращение полиномиального счета времени . Сокращение счета — это пара преобразований за полиномиальное время от входов другой задачи к входам данной задачи и от выходов данной задачи к выходам другой задачи, позволяющая решить другую задачу с использованием любой подпрограммы для данной задачи. проблема. Сокращение Тьюринга — это алгоритм для другой задачи, который выполняет полиномиальное количество вызовов подпрограммы для данной задачи и, помимо этих вызовов, использует полиномиальное время. В некоторых случаях используются экономные сокращения — более конкретный тип сокращения, сохраняющий точное количество решений.
#P-полные задачи по меньшей мере так же сложны, как и NP-полные . [1] Алгоритм с полиномиальным временем для решения #P-полной задачи, если бы он существовал, решил бы проблему P и NP, подразумевая, что P и NP равны. Такой алгоритм не известен, как и не известно доказательство того, что такой алгоритм не существует.
Примеры
[ редактировать ]Примеры #P-полных проблем включают в себя:
- Сколько различных назначений переменных будут удовлетворять данной общей логической формуле? ( #СБ )
- Сколько различных назначений переменных будет удовлетворять данной формуле ДНФ ?
- Сколько различных назначений переменных удовлетворят заданную задачу 2-выполнимости ?
- Сколько совершенных паросочетаний существует для данного двудольного графа ?
- Каково значение перманента данной матрицы, элементы которой равны 0 или 1? (См. #P-полнота 01-permanent .)
- Сколько существует раскрасок графа с использованием k цветов для конкретного графа G ?
- Сколько различных линейных расширений существует для данного частично упорядоченного множества или, что то же самое, сколько различных топологических упорядочений существует для данного ориентированного ациклического графа ? [2]
обязательно являются членами класса #P Все они также . В качестве примера рассмотрим случай подсчета решений задачи 1-выполнимости : ряда переменных, каждая из которых имеет индивидуальные ограничения, но не имеет никаких связей друг с другом. Решения можно эффективно подсчитать, умножив количество вариантов для каждой переменной в отдельности. Таким образом, эта проблема находится в #P , но не может быть #P-полной, если #P = FP . Это было бы удивительно, поскольку означало бы, что P = NP = PH .
Простые задачи с версиями жесткого подсчета
[ редактировать ]Некоторые #P-полные задачи соответствуют простым ( полиномиальным по времени ) задачам. Определить выполнимость булевой формулы в ДНФ несложно: такая формула выполнима тогда и только тогда, когда она содержит выполнимую конъюнкцию (ту, которая не содержит переменную и ее отрицание), тогда как подсчет количества удовлетворяющих присваиваний - это #P- полный. Более того, определить 2-выполнимость проще, чем подсчитать количество удовлетворяющих заданий. Топологическая сортировка проста в отличие от подсчета количества топологических сортировок. Единственное идеальное паросочетание можно найти за полиномиальное время, но подсчет всех идеальных паросочетаний является #P-полным. Задача подсчета идеальных паросочетаний была первой задачей подсчета, соответствующей простой P-задаче, которая оказалась #P-полной в статье Лесли Валианта 1979 года , которая также впервые определила класс #P и #P-полные задачи. [3]
Приближение
[ редактировать ]Существуют вероятностные алгоритмы , которые с высокой вероятностью возвращают хорошие приближения к некоторым #P-полным задачам. Это одна из демонстраций силы вероятностных алгоритмов.
Многие #P-полные задачи имеют полностью полиномиальную схему рандомизированной аппроксимации , или «FPRAS», которая, неформально, с высокой вероятностью дает аппроксимацию с произвольной степенью точности за время, полиномиальное как по отношению к размеру, так и по времени. задачи и требуемой степени точности. Джеррум , Валиант и Вазирани показали, что каждая #P-полная задача либо имеет FPRAS, либо ее практически невозможно аппроксимировать; если существует какой-либо алгоритм с полиномиальным временем, который последовательно создает аппроксимацию #P-полной задачи, которая находится в пределах полиномиального отношения к размеру входных данных точного ответа, то этот алгоритм можно использовать для построения FPRAS. [4]
Ссылки
[ редактировать ]- ^ Валиант, Лесли Г. (август 1979 г.). «Сложность задач перечисления и надежности» (PDF) . SIAM Journal по вычислительной технике . 8 (3): 410–421. дои : 10.1137/0208032 .
- ^ Брайтвелл, Грэм Р.; Винклер, Питер (1991). «Счет линейных расширений». Заказ . 8 (3): 225–242. дои : 10.1007/BF00383444 . S2CID 119697949 . .
- ^ Лесли Г. Валиант (1979). «Сложность вычисления перманента» . Теоретическая информатика . 8 (2). Эльзевир: 189–201. дои : 10.1016/0304-3975(79)90044-6 .
- ^ Марк Р. Джеррам; Лесли Дж. Валиант; Виджай В. Вазирани (1986). «Случайная генерация комбинаторных структур из равномерного распределения» . Теоретическая информатика . 43 . Эльзевир: 169–188. дои : 10.1016/0304-3975(86)90174-х .
Дальнейшее чтение
[ редактировать ]- Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. ISBN 3-540-65367-8 .