Проблема подсчета (сложность)

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без ссылок могут быть оспорены и удалены. Найти источники:  сложность «Проблема подсчета» – новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2014 г. ) ( Узнайте, как и когда удалять это сообщение )

В теории вычислительной сложности и теории вычислимости задача подсчета является типом вычислительной задачи . Если R является задачей поиска , то

${\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}$

— соответствующая счетная функция и

${\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}$

обозначает соответствующую проблему принятия решения.

Обратите внимание, что c _R является задачей поиска, в то время как # R является задачей принятия решений, однако c _R может быть сведено по методу C Кука к # R (для соответствующего C ) ​​с помощью бинарного поиска (причина, по которой # R определено именно так, а не является графиком c _R , заключается в том, чтобы сделать этот бинарный поиск возможным).

Так же, как NP имеет NP-полные проблемы посредством редукций ко многим единицам , #P имеет #P-полные проблемы посредством экономных редукций , преобразований проблем, которые сохраняют количество решений. ^[1]

• GapP

• "задача подсчета". PlanetMath .
• "класс сложности подсчета". PlanetMath .