Klass ♯P

Klass #P är en beräkningskomplexitetsklass som består av problem vars lösning är antalet framgångsrika (det vill säga slutar i accepterande tillstånd) beräkningsvägar för någon icke-deterministisk Turing-maskin som körs i polynomtid . Till exempel hör följande problem till denna klass:

Hur många olika Hamilton-cykler finns det i den givna grafen?
hur många olika vägar mellan två givna hörn finns det i den givna grafen?

Det är känt att P #P , en klass av problem som kan lösas av en Turing-maskin i polynomtid med hjälp av ett orakel för klass #P , innehåller komplexitetsklassen PH [1] . På grundval av detta anses #P -kompletta problem vara extremt komplexa när det gäller beräkningskomplexitet.

Ett av de mest välkända problemen som hör till klassen #P -komplett är problemet med att beräkna permanenten för en matris [2] :

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

i detta fall löses det till synes liknande problemet med att beräkna matrisdeterminanten i polynomtid.

Anteckningar

↑ Godel-priset 1998. Seinosuke Toda . Tillträdesdatum: 23 januari 2012. Arkiverad från originalet den 16 mars 2010. (obestämd)
↑ Leslie G. Valiant. The Complexity of Computing the Permanent (engelska) // Theoretical Computer Science . - Elsevier , 1979. - Vol. 8 , nr. 2 . - S. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .

Komplexitetsklasser av algoritmer
Anses som ljus	DLOGTIME AC 0 ACC 0 TC0 [ sv L SL RL NL NC SC CC P P-komplett ZPP RP BPP BQP EQP APX
Ska vara svårt	U.P. NP NP komplett co-NP co-NP-komplett AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplett
Anses vara svårt	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLA