Representación compacta del conjunto de soluciones de una instancia SAT

Esta pregunta ha surgido en mi mente después de leer las contribuciones de András Salamon y Colin McQuillan a mi pregunta anterior Soluciones de conteo de fórmulas Monotone-2CNF .

EDITAR 30 ^ª Mar 2011
pregunta Agregado n ° 2.

EDITAR 29 ^º Oct 2010
Pregunta reformuló después de la propuesta András su formalización a través de la noción de buena representación de un conjunto de soluciones (He modificado su noción un poco).

Sea una fórmula genérica de CNF con n variables. Sea S su conjunto de soluciones. Claramente | S | puede ser exponencial en n . Dejar$F$$n$$S$$|S|$$n$ ser una representación de S . Se dice que R esbuenosi y solo si los siguientes hechos son ciertos:$R$$S$$R$

1. tiene un tamaño polinómico en n .$R$$n$
2. permite enumerar las soluciones en S con retraso polinómico.$R$$S$
3. permite determinar | S | en tiempo polinómico (es decir, sin enumerar todas las soluciones). $R$$|S|$

Sería genial si fuera posible, en tiempo polinómico, construir tal para cada fórmula.$R$

Preguntas:

1. ¿Alguien demostró alguna vez que existe una familia de fórmulas para las que no puede existir una representación tan agradable ?
2. ¿Alguien estudió la relación entre la representación de y las simetrías exhibidas por F ? Intuitivamente, las simetrías deberían ayudar a representar de manera compacta S porque evitan la representación explícita de un subconjunto de soluciones S ′ ⊂ S cuando S ′ se reduce a una sola solución (es decir, de cada s i ∈ S ′ puede recuperar cada otro s j ∈ S ′ aplicando una simetría adecuada, por lo tanto cada s i ∈ S ′ es representativo del todo$S$$F$$S$$S' \subset S$$S'$$s_i \in S'$$s_j \in S'$$s_i \in S'$ )$S'$

Como se indicó (revisión 3), la pregunta tiene una respuesta simple: no.

La razón es que incluso para la clase altamente restringida de representaciones dadas por circuitos booleanos con compuertas AND, OR y NOT, no se conocen límites inferiores no triviales. (Claramente, un circuito que representa también representará S implícitamente, y es fácil enumerar las soluciones cambiando las entradas al circuito).$F$$S$

Para representaciones aún más restringidas, como circuitos monótonos o de profundidad constante, se conocen límites inferiores exponenciales. También hay límites inferiores exponenciales para representar fórmulas en forma CNF o DNF, aunque estos pueden verse como casos especiales de circuitos de profundidad constante. Finalmente, las representaciones de BDD pueden verse como formas compactas de DNF, pero existen fórmulas para las cuales el BDD requiere un tamaño exponencial para cualquier ordenamiento variable.

Para hacer su pregunta más precisa, considere la respuesta de @ Joshua con algún detalle y aclare lo que quiere decir con "trivial para enumerar cada solución".

Para la revisión 4, tenga en cuenta la declaración sobre el tamaño de BDD. Parte de lo que parece estar preguntando es: ¿hay una representación más compacta de las fórmulas DNF que las BDD? Supongamos que "BDD tiene un tamaño superpolinomial" significa "cada BDD que representa la misma función que B , independientemente del orden de las variables, tiene un tamaño superpolinomial", y que "buena representación" significa "una representación que permite enumerar las soluciones con retraso polinomial". Esta pregunta más específica se convierte en:$B$$B$

¿hay una familia de fórmulas y una buena representación que tenga un tamaño polinómico mientras que sus BDD tengan un tamaño superpolinómico?

¿Captura esto la esencia de lo que estás preguntando?

[Esta respuesta fue en respuesta a la versión anterior a la Revisión 6 del 29 de octubre de 2010.]

Creo que la pregunta funciona más o menos ahora, pero queda un problema técnico. A saber, cómo formalizar "es trivial enumerar todas las soluciones con solo mirar esa estructura". Una formalización quizás ingenua (pero la única que se me ocurrió en este momento) es la siguiente: dejemos que denote la representación del conjunto de soluciones S ( φ ) de φ . Por el momento no pongo ninguna restricción en R aparte de eso | R ( φ ) | ≤ p o l y ( n ) donde $R(\varphi)$$S(\varphi)$$\varphi$$R$$|R(\varphi)| \leq poly(n)$$\varphi$es un CNF en variables. Entonces queremos que haya un algoritmo A tal que A ( R ( φ ) ) = S ( φ ) y A en la entrada R ( φ ) ) se ejecute en el tiempo p o l y ( n , | S | ) .$n$$A$$A(R(\varphi)) = S(\varphi)$$A$$R(\varphi))$$poly(n, |S|)$

Bajo esta formalización, los únicos casos difíciles son aquellos en los que es superpolinomial pero sub-exponencial. Los casos restantes se manejan mediante la siguiente representación R y el algoritmo A : si | S | ≤ p o l y ( n ) , entonces sea R ( φ ) = ( 0 , S ) . Si | S | ≥ 2 Ω ( n ) entonces deje R ( φ ) = $S$$R$$A$$|S| \leq poly(n)$$R(\varphi) = (0, S)$$|S| \geq 2^{\Omega(n)}$ . A ( 0 , S ) simplemente genera S , y A ( 1 , φ ) simplemente calcula S por la fuerza bruta de φ . Desde | S | = 2 Ω ( n ) en el último caso, esto todavía se ejecuta en el tiempo O ( | S | ) .$R(\varphi) = (1, \varphi)$$A(0, S)$$S$$A(1, \varphi)$$S$$\varphi$$|S| = 2^{\Omega(n)}$$O(|S|)$

Sin embargo, los casos difíciles son en general imposibles bajo esta formalización. Si un tal y A existían, significaría que el p -tiempo-delimitada complejidad Kolmogorov de cada S se delimitada por p o l y ( n ) , que es absurdo (ya que casi todos los conjuntos S tienen máxima p -tiempo-limitado Complejidad de Kolmogorov, concretamente | S | ). (Aquí p es el tiempo de ejecución de A en función de | S | .)$R$$A$$p$$S$$poly(n)$$S$$p$$|S|$$p$$A$$|S|$

(Tenga en cuenta que si además requerimos que ejecute en el tiempo p o l y ( n , | φ | ) , la respuesta a la pregunta es no en general, suponiendo que P ≠ P r o m i s e U P : if φ tiene una solución única, entonces A ( R ( φ ) ) resolvería φ y correría a tiempo p o l y ( n ) .$R$$poly(n, |\varphi|)$$P \neq PromiseUP$$\varphi$$A(R(\varphi))$$\varphi$$poly(n)$