Проблема подсчета (сложность) - Counting problem (complexity)
В теории сложности вычислений и теории вычислимости , проблема подсчета является типом вычислительной задачи . Если R - проблема поиска, тогда
- соответствующая считающая функция и
обозначает соответствующую проблему решения.
Обратите внимание, что c R - это проблема поиска, в то время как # R - проблема решения, однако c R может быть уменьшено C Cook до # R (для соответствующего C ) с использованием двоичного поиска (причина # R определена так, как есть, скорее чем график c R , делает возможным этот бинарный поиск).
Подсчет класса сложности
Если NX - класс сложности, связанный с недетерминированными машинами, то #X = { #R | R ∈ NX } - это набор задач подсчета, связанных с каждой задачей поиска в NX . В частности, #P - это класс задач подсчета, связанных с задачами поиска NP . Подобно тому, как NP имеет NP-полные проблемы с помощью редукции до нескольких единиц, #P имеет полные проблемы с помощью экономных редукций , преобразований задач, которые сохраняют количество решений.
Смотрите также
внешние ссылки
| P ≟ NP | Эта статья по теоретической информатике незавершена . Вы можете помочь Википедии, расширив ее . |