Sharp-P Class

In complexity theory , #P is a class of problems whose solution is the number of successful, that is, completing in admitting states, computational paths for some non-deterministic Turing machine operating in polynomial time. For example, the following problems belong to #P :

How many different Hamiltonian cycles are there in a given graph?
How many different paths between two given vertices exist in a given graph?

Relationship with known difficulty classes

It is known that P ^#P , the class of problems solved by the Turing machine in polynomial time with the use of an oracle for the class #P , contains the complexity class PH ^[1] . Based on this, it is believed that #P- complete problems are extremely complex in terms of computational complexity.

Known # P-Complete Issues

One of the most well-known problems belonging to the class of #P -complete is the problem of calculating the permanent of a matrix ^[2] :

{\mbox{Per}}(A)=\sum _{\pi \in S_{n}}\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}},

{\ displaystyle {\ mbox {Per}} (A) = \ sum _ {\ pi \ in S_ {n}} \ prod _ {i = 1} ^ {n} a_ {i, \ pi _ {i}} = \ sum _ {\ pi \ in S_ {n}} a_ {1, \ pi _ {1}} a_ {2, \ pi _ {2}} \ cdots a_ {n, \ pi _ {n}}, }

{\mbox{Per}}(A)=\sum _{\pi \in S_{n}}\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}},

For comparison, at first glance a very similar problem of calculating the determinant of a matrix

{\mbox{det}}(A)=\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}},

{\ displaystyle {\ mbox {det}} (A) = \ sum _ {\ pi \ in S_ {n}} \ operatorname {sgn} (\ pi) \ prod _ {i = 1} ^ {n} a_ { i, \ pi _ {i}} = \ sum _ {\ pi \ in S_ {n}} \ operatorname {sgn} (\ pi) a_ {1, \ pi _ {1}} a_ {2, \ pi _ {2}} \ cdots a_ {n, \ pi _ {n}},}

{\mbox{det}}(A)=\sum _{\pi \in S_{n}}\operatorname {sgn}(\pi )\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}\operatorname {sgn}(\pi )a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}},

solved in polynomial time.

Links

↑ 1998 Gödel Prize. Seinosuke toda
↑ Leslie G. Valiant. The Complexity of Computing the Permanent // Theoretical Computer Science . - Elsevier , 1979. - Vol. 8 , no. 2 . - P. 189-201 . - DOI : 10.1016 / 0304-3975 (79) 90044-6 .

[1] 1998 Gödel Prize. Seinosuke toda

[2] Leslie G. Valiant. The Complexity of Computing the Permanent // Theoretical Computer Science . - Elsevier , 1979. - Vol. 8 , no. 2 . - P. 189-201 . - DOI : 10.1016 / 0304-3975 (79) 90044-6 .

Sharp-P Class

Relationship with known difficulty classes

Known # P-Complete Issues

Links

More articles: