Sharp-p-complete

Sharp-P-complete

#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. 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.