Sharp-P

The complexity class # P ( English pronunciation Sharp -P or P - Number ) is a class of so-called counting problems (as opposed to the complexity classes usually considered, the decision to treat problems ). Many # P problems are closely related to the corresponding NP- problems.

The class was introduced in 1979 by Leslie Valiant.

Definition

One problem is in the class # P if a non-deterministic Turing machine exists that is polynomial time bounded and for each instance of the problem has exactly as many accepting computation paths as there are solutions to the instance.

Example

A common decision problem in NP is the satisfiability of propositional logic (SAT):

• If at a given propositional formula a satisfying variable assignment?

The corresponding counting problem in # P is denoted by # SAT and reads:

• How many satisfying variable assignments there are to a given propositional formula?

Properties

By the theorem of Toda rich deterministic polynomial- time Turing machines that are allowed to provide a single oracle query to a problem from # P, to decide the languages ​​in PH. This is an indication of the enormous difficulty of # P problems to solve exactly. On the other hand, can be fully searched in polynomiellem place the computation tree of a non- deterministic polynomial time bounded Turing machine, so can all # P problems in polynomial space charge. This allows # P set in relation to other important complexity classes as follows:

List of some # P- complete problems

• # SAT
• Number of perfect matchings of a bipartite graph

• Permanent ( a 0-1 matrix)
• Number of linear extensions of a partial order