majority (more than half) of the computation paths accept. This finds the most significant bit in the #P problem answer. The decision problem class ⊕P (pronounced "Parity-P") instead asks for the least significant bit of the #P answer. Formal definitions #P is formally defined as follows: #P is the set of all functions such that there is a polynomial time nondeterministic Turing machine such that for all , equals the number of accepting branches in 's computation graph on . #P can also be equivalently defined in terms of a verifer. A decision problem is in NP if there exists a polynomial-time checkable certificate to a given problem instance—that is, NP asks whether there exists a proof of membership for the input that can be checked for correctness in polynomial time. The class #P asks how many certificates there exist for a problem instance that can be checked for correctness in polynomial time. In this context, #P is defined as follows: #P is the set of functions such that there exists a polynomial and a polynomial-time deterministic Turing machine , called the verifier, such that for every , . (In other words, equals the size of the set containing all of the polynomial-size certificates). History The complexity class #P was first defined by Leslie Valiant in a 1979 article on the computation of the permanent of a square matrix, in which he proved that permanent is #P-complete. Larry Stockmeyer has proved that for every #P problem there exists a randomized algorithm using an oracle for SAT, which given an instance of and returns with high probability a number such that . The runtime of the algorithm is polynomial in and . The algorithm is based on the leftover hash lemma. See also References External links Complexity classes