In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
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 sinc ...
, a counting problem is a type of
computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
. If ''R'' is a
search problem
In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If ''R'' is a binary relation such that field(''R'') ⊆ Γ+ and ''T'' is a Turing machine, then '' ...
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
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
(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
If ''NX'' is a complexity class associated with
non-deterministic machines then ''#X'' = is the set of counting problems associated with each
search problem
In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If ''R'' is a binary relation such that field(''R'') ⊆ Γ+ and ''T'' is a Turing machine, then '' ...
in ''NX''. In particular,
#P is the class of counting problems associated with
NP search problems.
Just as NP has
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
problems via
many-one reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the inst ...
s, #P has complete problems via
parsimonious reduction
In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another (a reduction) that preserves the number of solutions. Informally, it is a bijection between the respective sets of so ...
s, problem transformations that preserve the number of solutions.
See also
*
GapP
GapP is a counting complexity class, consisting of all of the functions ''f'' such that there exists a polynomial-time non-deterministic Turing machine ''M'' where, for any input ''x'', ''f(x)'' is equal to the number of accepting paths of ''M'' ...
External links
*
*
{{Comp-sci-theory-stub
Computational problems