HOME

TheInfoList



OR:

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 :c_R(x)=\vert\\vert \, is the corresponding counting function and :\#R=\ denotes the corresponding decision problem. Note that ''cR'' is a search problem while #''R'' is a decision problem, however ''cR'' 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 ''cR'', 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