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

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

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

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

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

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

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

Подсчет класса сложности

Если NX класс сложности, связанный с недетерминированный машины тогда #ИКС = {#Р | р ∈ NX} - это набор задач подсчета, связанных с каждым проблема поиска в NX. Особенно, #П класс задач счета, связанных с НП проблемы с поиском. НП-полный проблемы через много-одно сокращение, #P имеет полные проблемы через экономные скидки, преобразования задачи, сохраняющие количество решений.

Смотрите также

• GapP

внешняя ссылка

• "проблема подсчета". PlanetMath.
• «счет класса сложности». PlanetMath.