Luokka ♯P

Luokka #P on laskennallinen monimutkaisuusluokka , joka koostuu ongelmista, joiden ratkaisu on onnistuneiden (eli hyväksyviin tiloihin päättyvien) laskentapolkujen lukumäärä jollekin epädeterministiselle Turingin koneelle, joka kulkee polynomiajassa . Esimerkiksi seuraavat ongelmat kuuluvat tähän luokkaan:

Kuinka monta eri Hamiltonin sykliä annetussa kaaviossa on?
kuinka monta eri polkua annetussa graafissa on kahden annetun kärjen välillä?

Tiedetään, että P #P , ongelmaluokka, jonka Turingin kone voi ratkaista polynomiajassa käyttämällä oraakkelia luokassa #P , sisältää monimutkaisuusluokan PH [1] . Tältä pohjalta #P -täydellisiä ongelmia pidetään laskennallisen monimutkaisuuden kannalta erittäin monimutkaisina.

Yksi tunnetuimmista #P -täydellinen luokkaan kuuluvista ongelmista on matriisin pysyvän laskentaongelma [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}}

tässä tapauksessa näennäisesti samanlainen matriisideterminantin laskemisen ongelma ratkaistaan polynomiajassa.

Muistiinpanot

↑ 1998 Godel-palkinto. Seinosuke Toda . Käyttöpäivä: 23. tammikuuta 2012. Arkistoitu alkuperäisestä 16. maaliskuuta 2010. (määrätön)
↑ Leslie G. Valiant. The Complexity of Computing the Permanent (englanniksi) // Teoreettinen tietojenkäsittelytiede . - Elsevier , 1979. - Voi. 8 , ei. 2 . - s. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI