Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Counting problem (complexity)
Summary
In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then
is the corresponding counting function and
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 (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible).
If NX is a complexity class associated with non-deterministic machines then #X = {#R | R ∈ NX} is the set of counting problems associated with each search problem in NX. In particular, #P is the class of counting problems associated with NP search problems.
Just as NP has NP-complete problems via many-one reductions, #P has complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.