♯P-complet

classe de complexitat

En teoria de la complexitat, la classe de complexitat #P-Complet (es pronuncia "nombre P complet" o "hash P complet") és la classe dels problemes de decisió tals que son a dins la classe #P i son #P-hard, és a dir, qualsevol altre problema a #P es pot reduir a aquests problemes.[1]

Un algorisme de temps polinòmic que resolgui algun problema #P-complet resoldria el problema P = NP. No es coneix cap algorisme d'aquesta mena i se suposa que no n'existeix cap, tot i que no hi ha cap demostració.

Alguns exemples de problemes d'aquesta classe son els següents:[2]

Referències modifica

  1. V., Vazirani, Vijay. Approximation algorithms. Berlín: Springer, 2001. ISBN 3540653678. 
  2. «The complexity of computing the permanent» (en anglès). Theoretical Computer Science, 8, 2, 01-01-1979, pàg. 189–201. DOI: 10.1016/0304-3975(79)90044-6. ISSN: 0304-3975.