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

#Pcomplete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory. A problem is #Pcomplete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomialtime counting reduction, i.e. a polynomialtime Turing reduction relating the cardinalities of solution sets.^{[citation needed]} Equivalently, a problem is #Pcomplete if and only if it is in #P, and for any nondeterministic 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 #Pcomplete problems include:
A polynomialtime algorithm for solving a #Pcomplete 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 
