1) ¿Es posible tener una reducción parsimoniosa de un problema # P completo #A a un problema de conteo #B cuando (la versión de decisión) A es NP-completa y B está en P?
Por ejemplo, ¿puede haber una reducción parsimoniosa de #SAT a #B, cuando B está en P?
2) Si B está en P, ¿cuáles son las diferentes posibilidades para la complejidad de #B?
Si insiste en reducciones parsimoniosas (donde se preserva el número de soluciones), no puede tener tal reducción a menos que P = NP porque el algoritmo de decisión para el no vacío de soluciones para B le dará un algoritmo de decisión para el no vacío de soluciones para R. Por otro lado, si permite otro tipo de reducciones, puede tener ese caso. Por ejemplo, Valiant demostró que #SAT se reduce al problema de contar emparejamientos perfectos en un gráfico bipartito: la reducción comienza con una fórmula CNF y construye un gráfico bipartito G cuyo número de emparejamientos perfectos mod 2 8 m + 1 es 4 m multiplicado por el número de asignaciones satisfactorias de F , donde
Vea el Capítulo 18 en el libro "Complejidad computacional" de Papadimitriou para una exposición clara de esto.
La respuesta a la pregunta 2 es que la complejidad del problema de conteo #B puede ser básicamente cualquier cosa (ni siquiera necesariamente computable). Más precisamente, la restricción de que la versión de decisión está en P no tiene ninguna implicación en la complejidad de la versión de conteo. Esto se debe a que puede agregar una solución ficticia a cualquier problema de relación para que la versión de decisión se vuelva trivial (la respuesta siempre es sí) sin cambiar la complejidad de la versión de conteo.