In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
and
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, a counting problem is a type of
computational problem
In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computati ...
. If ''R'' is a
search problem then
:
is the corresponding
counting function and
:
denotes the corresponding decision problem.
Note that ''c
R'' is a search problem while #''R'' is a decision problem, however ''c
R'' can be ''C''
Cook-reduced to #''R'' (for appropriate ''C'') using a
binary search (the reason #''R'' is defined the way it is, rather than being the graph of ''c
R'', is to make this binary search possible).
Counting complexity class
Just as NP has
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
problems via
many-one reductions, #P has #P-complete problems via
parsimonious reductions, problem transformations that preserve the number of solutions.
See also
*
GapP
References
External links
*
*
Computational problems
{{Comp-sci-theory-stub