Problema: Dado representado por un circuito booleano, genera una uniformemente aleatoria tal que (o salida si no existe tal ).
Claramente este problema es NP-duro. Mi pregunta es si este problema también es "NP-fácil":
Pregunta: ¿Existe un algoritmo que resuelva el problema anterior en el polinomio temporal en el tamaño del circuito de dado acceso a un oráculo SAT?
Alternativamente, ¿hay un algoritmo de tiempo polinomial suponiendo NP = P?
Claramente, tener acceso a un oráculo #SAT es suficiente, por lo que la complejidad se encuentra en algún lugar entre NP y #P.
Siento que esto debería haberse estudiado antes, pero no puedo encontrar una respuesta en Google.
Sé cómo resolver el problema aproximadamente (es decir, generar una tarea satisfactoria que sea estadísticamente cercana al uniforme) usando una variante del teorema de Valiant-Vazirani y / o un conteo aproximado, pero conseguir un uniforme exacto parece ser un problema diferente.
fuente