Osztály ♯P

A #P osztály egy számítási összetettségi osztály , amely olyan problémákból áll, amelyek megoldása a sikeres (azaz elfogadó állapotokban végződő) számítási útvonalak száma néhány nemdeterminisztikus Turing-gép esetében, amely polinomiális időben fut . Például a következő problémák tartoznak ebbe az osztályba:

Hány különböző Hamilton-ciklus van az adott gráfban?
hány különböző út van két adott csúcs között az adott gráfban?

Ismeretes, hogy a P #P , egy Turing-géppel polinomiális időben megoldható problémák egy orákulum segítségével #P osztályhoz , tartalmazza a PH [1] összetettségi osztályt . Ezen az alapon a #P -teljes problémákat a számítási komplexitás szempontjából rendkívül összetettnek tekintik.

A #P -teljes osztályhoz tartozó egyik legismertebb probléma a mátrix állandójának kiszámítása [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}}

ebben az esetben a mátrixdetermináns számításának hasonlónak tűnő problémája polinomiális időben megoldódik.

Jegyzetek

↑ 1998-as Godel-díj. Seinosuke Toda . Hozzáférés dátuma: 2012. január 23. Az eredetiből archiválva : 2010. március 16. (határozatlan)
↑ Leslie G. Valiant. The Complexity of Computing the Permanent (angol) // Theoretical Computer Science . - Elsevier , 1979. - Vol. 8 , sz. 2 . - P. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES