¿Límites inferiores en #SAT?

El problema #SAT es el problema canónico # P-complete. Es un problema funcional más que un problema de decisión. Pregunta, dada una fórmula booleana en lógica proposicional, cuántas asignaciones satisfactorias tiene¿Cuáles son los mejores límites inferiores en #SAT?$F$$F$

Que yo sepa, nadie ha descubierto cómo explotar la propiedad de "soluciones de conteo" de #SAT en ningún límite inferior en algoritmos deterministas, por lo que desafortunadamente los límites inferiores más conocidos para #SAT son básicamente los mismos que para SAT.

Sin embargo, ha habido un pequeño progreso. Tenga en cuenta que la versión de decisión de #SAT se llama "Majority-SAT": dada una fórmula, ¿al menos la de las posibles asignaciones la satisfacen? $1/2$"Majority-SAT" es completo, y dado un algoritmo para Majority-SAT, uno puede resolver #SAT con llamadas al algoritmo.$PP$$O(n)$

Lo más cerca que las personas han llegado a nuevos límites inferiores para #SAT (que no se sabe que tienen para SAT) es con límites inferiores para "Mayoría-de-Mayoría-SAT": dada una fórmula proposicional sobre dos conjuntos de variables X e Y , para al menos la de las posibles asignaciones a , ¿es cierto que al menos la de las asignaciones a hacen que la fórmula sea satisfactoria? $1/2$$X$$1/2$$Y$Este problema está en el "segundo nivel" de la jerarquía de conteo (la clase ). Los límites inferiores del espacio de tiempo cuántico (y más) son conocidos para esta clase.$PP^{PP}$

La encuesta en http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf ofrece una visión general de los resultados en esta dirección.

Además, #SAT no tiene un esquema de aproximación aleatorio totalmente polinómico (FPRAS) a menos que .$NP=RP$