Counting problem (complexity)
Type of computational problem / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Counting problem (complexity)?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then
This article needs additional citations for verification. (October 2014) |
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).