Sharp-P
Encyclopedia
In computational complexity theory
, the complexity class #P is the set of the counting problems associated with the decision problem
s in the set NP
. More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problem
s but a class of function problem
s.
An NP problem is often of the form, "Are there any solutions that satisfy certain constraints?" For example:
The corresponding #P problems ask "how many" rather than "are there any". For example:
Clearly, a #P problem must be at least as hard as the corresponding NP problem. If it's easy to count answers, then it must be easy to tell whether there are any answers. Just count them, and see if the count is greater than zero.
One consequence of Toda's theorem
is that a polynomial-time machine with a #P oracle
(P#P) can solve all problems in PH, the entire polynomial hierarchy
. In fact, the polynomial-time machine only needs to make one #P query to solve any problem in PH. This is an indication of the extreme difficulty of solving #P-complete problems exactly.
Surprisingly, some #P problems that are believed to be difficult correspond to easy P
problems. For more information on this, see #P-complete.
The closest decision problem class to #P is PP
, which asks if a 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 instead asks for the least significant bit of the #P answer.
The complexity class #P was first defined by Leslie Valiant
in a 1979 paper on the computation of the permanent
, in which he proved that permanent is #P-complete
.
Larry Stockmeyer
has proved that for every #P problem P there exists a randomized algorithm using oracle for SAT, which given an instance a of P and ε>0 returns with high probability a number x such that
. The runtime of the algorithm is polynomial in a and 1/ε. The algorithm is based on leftover hash lemma.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class #P is the set of the counting problems associated with the decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s in the set NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
. More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s but a class of function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
s.
An NP problem is often of the form, "Are there any solutions that satisfy certain constraints?" For example:
- Are there any subsets of a list of integers that add up to zero? (subset sum problem)
- Are there any Hamiltonian cycles in a given graphGraph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
with cost less than 100? (traveling salesman problem) - Are there any variable assignments that satisfy a given CNFConjunctive normal formIn Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
formula? (Boolean satisfiability problemBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
)
The corresponding #P problems ask "how many" rather than "are there any". For example:
- How many subsets of a list of integers add up to zero?
- How many Hamiltonian cycles in a given graph have cost less than 100?
- How many variable assignments satisfy a given CNF formula?
Clearly, a #P problem must be at least as hard as the corresponding NP problem. If it's easy to count answers, then it must be easy to tell whether there are any answers. Just count them, and see if the count is greater than zero.
One consequence of Toda's theorem
Toda's theorem
Toda's theorem was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P...
is that a polynomial-time machine with a #P oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
(P#P) can solve all problems in PH, the entire polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
. In fact, the polynomial-time machine only needs to make one #P query to solve any problem in PH. This is an indication of the extreme difficulty of solving #P-complete problems exactly.
Surprisingly, some #P problems that are believed to be difficult correspond to easy P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
problems. For more information on this, see #P-complete.
The closest decision problem class to #P is PP
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
, which asks if a 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 instead asks for the least significant bit of the #P answer.
The complexity class #P was first defined by Leslie Valiant
Leslie Valiant
Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
in a 1979 paper on the computation of the permanent
Permanent
The permanent of a square matrix in linear algebra, is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix...
, in which he proved that permanent is #P-complete
Permanent is sharp-P-complete
In a 1979 paper Leslie Valiant proved that the problem of computing the permanent of a matrix is #P-hard, and remains #P-complete even if the matrix is restricted to have entries that are all 0 or 1. This result is sometimes known as Valiant's theorem and is considered a seminal result in...
.
Larry Stockmeyer
Larry Stockmeyer
Larry Joseph Stockmeyer was a computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing...
has proved that for every #P problem P there exists a randomized algorithm using oracle for SAT, which given an instance a of P and ε>0 returns with high probability a number x such that
. The runtime of the algorithm is polynomial in a and 1/ε. The algorithm is based on leftover hash lemma.