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

$c_R(x)=\vert\{y\mid R(x,y)\}\vert \,$

is the corresponding counting function and

$\#R=\{(x,y)\mid y\leq c_R(x)\}$

denotes the corresponding counting 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 (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

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.

This article incorporates material from counting problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article incorporates material from counting complexity class on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Theoretical computer science stubs Computational problems Wikimedia Foundation. 2010. Игры ⚽ Поможем сделать НИР Cell counting If Women Counted Look at other dictionaries: Counting problem — may refer to: Enumeration Combinatorial enumeration Counting problem (complexity) This disambiguation page lists articles associated with the same title. If an internal …   Wikipedia Counting problem (computability theory) — In computability theory, a counting problem is a type of computational problem. If R is a search problem then :c R(x)=vert{ymid R(x,y)}vert ,is the corresponding counting function and:#R={(x,y)mid yleq c R(x)}denotes the corresponding counting… …   Wikipedia Counting — is the action of finding the number of elements of a finite set of objects. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for every element of the set, in some order, while marking (or… …   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 Optimization problem — In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or… …   Wikipedia Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… …   Wikipedia Counting points on elliptic curves — An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields… …   Wikipedia Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia Computational problem — In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring Given a positive integer n, find a nontrivial prime …   Wikipedia Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”