В теории сложности вычислений класс сложности #P (произносится как «острый P» или иногда «число P» или «хэш P») представляет собой набор задач подсчета, связанных с проблемами решения в наборе NP . Более формально, #P - это класс функциональных задач вида «вычислить f ( x )», где f - количество принимающих путей недетерминированной машины Тьюринга, работающей за полиномиальное время . В отличие от большинства известных классов сложности, это не класс задач решения, а класс функциональных задач.. Самые сложные репрезентативные проблемы этого класса являются # P-полными .
Отношение к проблемам решения
NP проблема решения часто в форме «Есть ли какое - либо решение , которые удовлетворяют определенные ограничения?» Например:
- Есть ли в списке целые подмножества, которые в сумме дают ноль? ( проблема суммы подмножества )
- Существуют ли гамильтоновы циклы в данном графе стоимостью менее 100? ( задача коммивояжера )
- Существуют ли какие-либо присвоения переменных, которые удовлетворяют данной формуле CNF (конъюнктивной нормальной формы) ? ( Задача логической выполнимости или SAT)
- Имеет ли одномерный действительный многочлен положительные корни? ( Корневой поиск )
Соответствующие задачи с функцией #P спрашивают «сколько», а не «есть ли какие-нибудь». Например:
- Сколько подмножеств списка целых чисел в сумме дают ноль?
- Сколько гамильтоновых циклов в данном графе стоили меньше 100?
- Сколько присвоений переменных удовлетворяют данной формуле CNF?
- Сколько корней действительного многочлена одной переменной положительны?
Насколько это сложно?
Ясно, что проблема #P должна быть не менее сложной, чем соответствующая проблема NP . Если подсчитать ответы легко, то должно быть легко определить, есть ли какие-нибудь ответы - просто посчитайте их и посмотрите, больше ли счетчик нуля. Некоторые из этих проблем, такие как поиск корня , достаточно легко решить в FP , в то время как другие являются # P-завершенными .
Одним из следствий теоремы Toda в том , что полиномиальное время машин с #P оракулом ( P #P ) может решить все проблемы в PH , весь многочлен иерархию . Фактически, машине полиномиального времени достаточно сделать только один запрос #P, чтобы решить любую проблему в PH . Это указывает на крайнюю сложность точного решения #P -полных задач.
Удивительно, но некоторые задачи #P , которые считаются сложными, соответствуют простым (например, линейному времени) P- задачам. Для получения дополнительной информации см. # P-complete .
Ближайшим к #P классом задач решения является PP , который спрашивает, принимает ли большинство (более половины) путей вычисления. Это находит самый старший бит в ответе на проблему #P . Класс задачи решения ⊕P (произносится как «Четность-P») вместо этого запрашивает младший бит ответа #P .
Формальные определения
#P формально определяется следующим образом:
- #P - это набор всех функций такая, что существует недетерминированная машина Тьюринга с полиномиальным временем такое, что для всех , равно количеству принимающих веток в график вычислений на . [1]
#P также может быть эквивалентно определено в терминах верифера. Проблема принятия решения заключается в NP, если существует проверяемый за полиномиальное время сертификат для данного экземпляра проблемы, то есть NP спрашивает, существует ли доказательство принадлежности для ввода, правильность которого можно проверить за полиномиальное время. Класс #P спрашивает, сколько существует сертификатов для экземпляра проблемы, правильность которых можно проверить за полиномиальное время. [1] В этом контексте #P определяется следующим образом:
- #P - это набор функций такой, что существует многочлен и детерминированная машина Тьюринга с полиномиальным временем , называется верификатором, так что для каждого , . [2] (Другими словами, равен размеру набора, содержащего все сертификаты полиномиального размера).
История
Класс сложности #P был первым определен Лесли Валиант в 1979 статье о вычислении постоянного из квадратной матрицы , в которой он доказал , что перманент # P-полной . [3]
Ларри Стокмейер доказал, что для каждой проблемы #Pсуществует рандомизированный алгоритм с использованием оракула для SAT, которому дан экземпляр из а также возвращает с высокой вероятностью число такой, что . [4] Время выполнения алгоритма полиномиально от а также . Алгоритм основан на лемме об оставшихся хэшах .
Смотрите также
Рекомендации
- ^ а б Варак, Вооз (весна 2006 г.). «Сложность подсчета» (PDF) . Компьютерные науки 522: вычислительная сложность . Университет Принстона.
- ^ Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. п. 344. ISBN 978-0-521-42426-4.
- ^ Лесли Г. Валиант (1979). «Сложность вычисления постоянного». Теоретическая информатика . Эльзевир . 8 (2): 189–201. DOI : 10.1016 / 0304-3975 (79) 90044-6 .
- ^ Стокмейер, Ларри (ноябрь 1985). «Об алгоритмах аппроксимации для #P» (PDF) . SIAM Journal on Computing . 14 (4): 849. DOI : 10,1137 / 0214060 . Архивировано из оригинала (PDF) на 2009 резюме Lay .
Внешние ссылки
- Зоопарк сложности : Класс #P