Clase ♯P

La clase #P  es una clase de complejidad computacional que consta de problemas cuya solución es el número de rutas de cálculo exitosas (es decir, que terminan en estados de aceptación) para alguna máquina de Turing no determinista que se ejecuta en tiempo polinomial . Por ejemplo, los siguientes problemas pertenecen a esta clase:

• ¿Cuántos ciclos hamiltonianos diferentes hay en el gráfico dado?
• ¿Cuántos caminos diferentes hay entre dos vértices dados en el gráfico dado?

Se sabe que P #P  , una clase de problemas que pueden ser resueltos por una máquina de Turing en tiempo polinomial usando un oráculo para la clase #P  , contiene la clase de complejidad PH [1] . Sobre esta base, los problemas # P -completos se consideran extremadamente complejos en términos de complejidad computacional.

Uno de los problemas más conocidos pertenecientes a la clase #P -completa es el problema de calcular la permanente de una matriz [2] :

en este caso, el problema aparentemente similar de calcular el determinante de la matriz se resuelve en tiempo polinomial.

Notas

1. ↑ Premio Gödel 1998. Seinosuke Toda . Fecha de acceso: 23 de enero de 2012. Archivado desde el original el 16 de marzo de 2010. (indefinido)
2. ↑ Leslie G. valiente. La Complejidad de Computar lo Permanente  (Español)  // Informática Teórica . - Elsevier , 1979. - Vol. 8 , núm. 2 . - pág. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .