Třída ♯P

Třída #P je třída výpočetní složitosti sestávající z problémů, jejichž řešením je počet úspěšných (tj. končících akceptováním stavů) výpočetních cest pro nějaký nedeterministický Turingův stroj běžící v polynomiálním čase . Do této třídy patří například následující problémy:

Kolik různých hamiltonovských cyklů je v daném grafu?
kolik různých cest mezi dvěma danými vrcholy je v daném grafu?

Je známo, že P #P , třída problémů, které lze vyřešit Turingovým strojem v polynomiálním čase pomocí orákula pro třídu #P , obsahuje třídu složitosti PH [1] . Na tomto základě jsou #P -kompletní problémy považovány za extrémně složité z hlediska výpočetní složitosti.

Jedním z nejznámějších problémů patřících do třídy #P -complete je problém výpočtu permanentu matice [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}}

v tomto případě se zdánlivě podobný problém výpočtu maticového determinantu řeší v polynomiálním čase.

Poznámky

↑ Godelova cena 1998. Seinosuke Toda . Datum přístupu: 23. ledna 2012. Archivováno z originálu 16. března 2010. (neurčitý)
↑ Leslie G. Valiant. The Complexity of Computing the Permanent (anglicky) // Theoretical Computer Science . - Elsevier , 1979. - Sv. 8 , č. 2 . - S. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY