Counting problem (computability theory)
- Counting problem (computability theory)
In 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 counting 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).
Counting complexity class
If "NC" is a complexity class associated with non-deterministic machines then "#C" = {"#R" | "R" ∈ "NC"} is the set of counting problems associated with each search problem in "NC". In particular, #P is the class of counting problems associated with NP search problems.
:planetmath|id=3439|title=counting problem:planetmath|id=3444|title=counting complexity class
Wikimedia Foundation.
2010.
Look at other dictionaries:
Counting problem (complexity) — 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 counting problem. Note that cR… … Wikipedia
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia
Decision problem — A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes or no answer,… … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia
Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… … Wikipedia
Model theory — This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields,… … Wikipedia
Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… … Wikipedia
Philosophy of mathematics — The philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. The aim of the philosophy of mathematics is to provide an account of the nature and methodology of … Wikipedia
Outline of discrete mathematics — The following outline is presented as an overview of and topical guide to discrete mathematics: Discrete mathematics – study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have… … Wikipedia
Logicism — is one of the schools of thought in the philosophy of mathematics, putting forth the theory that mathematics is an extension of logic and therefore some or all mathematics is reducible to logic.[1] Bertrand Russell and Alfred North Whitehead… … Wikipedia
