Sharp-P-complete

related topics
{math, number, function}
{rate, high, increase}

#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory. A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction, i.e. a polynomial-time Turing reduction relating the cardinalities of solution sets.[citation needed] Equivalently, a problem is #P-complete if and only if it is in #P, and for any non-deterministic Turing machine ("NP machine"), the problem of computing its number of accepting paths can be reduced to this problem.[citation needed]

Very often the reductions are "parsimonious," i.e., they preserve the number of solutions.[citation needed]

Examples of #P-complete problems include:

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = PH, and thus P = NP. No such algorithm is currently known.

Contents

Full article ▸

related documents
Concatenation
Graph of a function
Quadratic programming
Unique factorization domain
Equality (mathematics)
General number field sieve
Snake lemma
Currying
Bogosort
Binary operation
Closed set
Haar wavelet
Domain (mathematics)
Hamming distance
Bucket sort
Data integrity
Generating set of a group
Boundary (topology)
Alexandroff extension
Bijection
Symbolic logic
Alternating group
Removable singularity
Recursively enumerable language
Heap (data structure)
Directed set
Fibonacci coding
Axiom of extensionality
Waring's problem
Hilbert's fifth problem