Sharp-P
The complexity class #P ( English pronunciation Sharp-P or Number-P ) is a class of so-called counting problems (in contrast to the most frequently considered complexity classes that deal with decision problems). Many # P problems are closely related to the associated NP problems.
The class was introduced by Leslie Valiant in 1979 .
definition
A problem is in the class #P if there is a nondeterministic Turing machine which is polynomially time-limited and for each instance of the problem has exactly as many accepting computation paths as there are solutions to the instance .
example
A well-known decision problem from NP is the satisfiability problem of propositional logic (SAT):
- Does a satisfying variable assignment exist for a given propositional formula?
The corresponding counting problem from #P is denoted by #SAT and is:
- How many fulfilling variable assignments are there for a given propositional formula?
properties
According to Toda's theorem, deterministic polynomial time-limited Turing machines, which are allowed to make a single oracle query to a problem from #P, are sufficient to decide the languages in PH . This is an indication of the enormous difficulty in solving #P problems exactly. On the other hand, the calculation tree of a nondeterministic, polynomial time-limited Turing machine can be searched completely in polynomial space, so that all # P problems can be calculated in polynomial space. This means that #P can be related to other important complexity classes as follows:
List of some # P-complete problems
- #SAT
- Number of perfect matchings of a bipartite graph
- This fact is particularly interesting because the associated decision problem ( existence of perfect matchings in bipartite graphs) can be solved deterministically in polynomial time.
- Permanent (a 0-1 matrix)
- Number of linear extensions of a partial order
literature
- Leslie G. Valiant: The complexity of computing the permanent . Theoretical Computer Science, 8: 189-201, 1979
- Graham Brightwell, Peter Winkler: Counting linear extensions, Order, Volume 8, Issue 3, Sep 1991, Pages 225 - 242, doi : 10.1007 / BF00383444
Web links
- #P . In: Complexity Zoo. (English)