Введение
Класс сложности
В теории вычислительной сложности класс сложности #P (произносится как "шарп P" или, иногда "число P" или "хэш P") — это множество задач подсчёта, связанных с задачами принятия решений в множестве NP. Более формально, #P — это класс функциональных задач вида "вычислить f(x)", где f — число принимающих путей недетерминированной машины Тьюринга, работающей за полиномиальное время. В отличие от большинства известных классов сложности, это не класс задач принятия решений, а класс функциональных задач. Наиболее сложные, представительные задачи этого класса — #P-полные.
Связанные классы сложности
Очевидно, что задача #P должна быть как минимум не проще, чем соответствующая задача NP. Если легко подсчитать количество решений, то должно быть легко определить, существуют ли решения вообще – достаточно подсчитать их и проверить, превышает ли полученное число ноль. Некоторые из этих задач, такие как нахождение корней, достаточно просты для класса FP, в то время как другие являются #P-полными. Одним из следствий теоремы Тоды является то, что машина времени с полиномиальной сложностью, использующая #P-оракул (P#P), может решить все задачи в PH – всю полиномиальную иерархию. Фактически, машине времени с полиномиальной сложностью достаточно сделать всего один #P-запрос для решения любой задачи в PH. Это указывает на чрезвычайную сложность точного решения #P-полных задач. Удивительно, но некоторые #P-задачи, считающиеся сложными, соответствуют простым (например, с линейной временной сложностью) P-задачам. Более подробную информацию можно найти в статье #P complete. Ближайшим классом задач принятия решений к #P является PP, который определяет, принимает ли большинство (более половины) путей вычислений. Это позволяет найти старший значащий бит ответа на задачу #P. Класс задач принятия решений ⊕P (произносится "Паритет P") вместо этого запрашивает младший значащий бит ответа #P.
История
Класс сложности #P был впервые определен Лесли Валиантом в статье 1979 года, посвященной вычислению постоянного определителя квадратной матрицы, в которой он доказал, что задача о вычислении постоянного определителя является #P-полной. Ларри Стокмейер доказал, что для каждой задачи из класса #P существует рандомизированный алгоритм, использующий оракул для SAT, который, получив на вход экземпляр задачи, с высокой вероятностью возвращает число, такое что. Время работы алгоритма полиномиально зависит от размера входных данных, а алгоритм основан на лемме об остаточном хешировании.