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