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
In computational complexity theory and computability theory, a search problem is a computational problem of finding
an ''admissible'' answer for a given input value, provided that such an answer exists. In fact, a search problem is specified by a b ...
then
:
is the corresponding
counting function
Counting is the process of determining the number of elements of a finite set of objects; that is, determining the size of a set. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for ever ...
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 m ...
(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 reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether ...
s, #P has #P-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 sol ...
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' ...
References
External links
*
*
Computational problems
{{Comp-sci-theory-stub