В теории сложности вычислений и теории вычислимости задача подсчета является разновидностью вычислительной задачи . Если R — задача поиска , то
– соответствующая считающая функция и
обозначает соответствующую проблему решения.
Обратите внимание, что c R — это проблема поиска, в то время как # R — это проблема принятия решения, однако c R может быть сведена C Куком к # R (для соответствующего C ) с использованием двоичного поиска (причина # R определяется так, как она есть, а не чем быть графиком c R , это сделать возможным этот двоичный поиск).
Если NX — класс сложности, связанный с недетерминированными машинами, то #X = { #R | R ∈ NX } — множество задач счета, связанных с каждой задачей поиска в NX . В частности, #P — это класс задач счета, связанных с задачами поиска NP . Точно так же, как NP имеет NP-полные проблемы посредством сокращений «многие единицы» , #P имеет полные проблемы посредством экономных сокращений , преобразований задач, которые сохраняют количество решений.
