Común
Numeral-P
clase de complejidad
Numeral-P
En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral-P) es el conjunto de los problemas de conteo asociados a los problemas de decisión en el conjunto NP. Un problema en NP se describe usualmente con la pregunta ¿Existe una solución que satisface una cierta restricción?, por ejemplo: ¿Existe algún subconjunto de enteros cuya suma de elementos sea cero? (Problema de suma de subconjuntos) ¿Existe algún ciclo Hamiltoniano en un grafo dado con costo inferior a 100? (Problema del agente viajero) ¿Existe alguna asignación de variables que satisfaga una expresión booleana? (Problema de satisfacibilidad booleana) Los problemas correspondientes en #P se interesan en saber cuantos elementos satisfacen la pregunta en lugar de si existe algún elemento que la satisfaga. Por ejemplo: ¿Cuántos subconjuntos de enteros tiene un conjunto cuya suma de elementos sea cero? ¿Cuántos ciclos Hamiltonianos en un grafo tienen costo inferior a 100? ¿Cuántas asignaciones de…
Abre sobres, colecciona cartas y cámbialas. Gratis.
Jugar gratis