¿Un teorema de suma directa para la complejidad del espacio de la cláusula de resolución?

La resolución es un esquema para demostrar la insatisfacción de los CNF. Una prueba en resolución es una deducción lógica de la cláusula vacía para las cláusulas iniciales de la CNF. En particular, se puede inferir cualquier cláusula inicial, y de dos cláusulas $A \lor x$ y $B \lor \neg{x}$ la cláusula $A \lor B$ se puede deducir. Una refutación es una secuencia de deducciones que termina con una cláusula vacía.

Si se implementa dicha refutación, podemos considerar un procedimiento que mantenga algunas cláusulas en la memoria. En caso de que una cláusula no inicial se deba usar nuevamente y ya no esté en la memoria, el algoritmo debe hacerlo nuevamente desde cero o desde los que están en la memoria.

Deje $Sp(F)$ el menor número de cláusulas que se guardarán en la memoria para alcanzar las cláusulas vacías. Esto se llama el espacio de la cláusula complejidad de $F$ . Decimos decir que $Sp(F)=\infty$ es $F$ es satisfactoria.

El problema que sugiero es el siguiente: considere dos CNF $A=\bigwedge_{i=1}^m A_i$ y $B=\bigwedge_{j=1}^n B_j$ , y deje que el CNF

A \lor B = ⋀_{i = 1}^{m} ⋀_{j = 1}^{n} A_{i} \lor B_{j}

$A \lor B = \bigwedge_{i=1}^m \bigwedge_{j=1}^n A_i \lor B_j$

¿Cuál es la relación de $Sp(A \lor B)$ con $Sp(A)$ y $Sp(B)$ ?

El límite superior obvio es $Sp(A \lor B) \leq Sp(A) + Sp(B) -1$ . ¿Esto es apretado?

cc.complexity-theory lo.logic proof-complexity proof-search MassimoLauria
fuente

¡Buena pregunta! ¿Conoces la respuesta para el tamaño de la suma directa? Supongo que el peor de los casos es cuando A y B no tienen variables compartidas. Un caso interesante podría ser cuando A y B son iguales hasta cambiar el nombre de la variable. Por cierto, no veo cómo consigues ese límite superior, parece que puede ser mucho peor.

Kaveh

Ahora veo el límite superior, puede copiar la refutación de

para

para obtener

uno en uno por cada

y luego hacer la refutación por

. El tamaño será de alrededor de

B

$B$

A_{i} \lor B_{j}

$A_i \lor B_j$

1 \leq j \leq n

$1 \leq j \leq n$

A_{i}

$A_i$

1 \leq i \leq m

$1 \leq i \leq m$

A

$A$

m . (S i z e (B) + O (1)) + S i z e (A)

$m.(Size(B)+O(1))+Size(A)$ .

Kaveh

Tienes razón. Olvidé mencionar eso, pero, por supuesto, el caso más interesante en términos de un límite inferior es cuando A y B no comparten variables. Eso es exactamente el caso que estoy realmente interesado en. Teniendo en cuenta diferentes A y B es mejor inductivamente obtener un resultado de

, donde

son variables copias disjuntas de la misma

F_{1} \lor F_{2} \lor \dots F_{k}

$F_1 \lor F_2 \lor \ldots F_k$

F_{i}

$F_i$

F

$F$

MassimoLauria

Tenga en cuenta que con respecto a la longitud de refutación, fácilmente tiene

L e n g t h (A \lor B) \leq L e n g t h (B) | A | + L e n g t h (A)

$Length(A \lor B) \leq Length(B)|A|+Length(A)$

MassimoLauria

El límite superior del espacio trivial en realidad requiere una cláusula menos en la memoria. Edité en consecuencia.

MassimoLauria

Respuestas:

Quería publicar esto como un comentario, pero dado que no puedo entender la forma de hacerlo, supongo que tendrá que ser una "respuesta" en su lugar.

Estoy de acuerdo en que la pregunta es buena. Por supuesto, la misma pregunta también se puede hacer sobre la duración de las refutaciones de resolución (es decir, el número de cláusulas que ocurren en la refutación, contadas con repeticiones) y el ancho de la refutación (es decir, el tamaño o el número de literales que ocurren en , la cláusula más grande en la refutación).

En todos estos casos hay límites superiores "obvios", pero no me queda claro si uno debería esperar igualar los límites inferiores o no. Por lo tanto, quería agregar una pregunta y un comentario.

La pregunta se refiere a la duración de la refutación. Parece razonable creer que el límite de duración establecido en el comentario de Massimo es estrecho, pero ¿sabemos esto?

Y el comentario se refiere al ancho. Tenga en cuenta que para esta medida, un momento de pensamiento revela que no se cumple un límite inferior de suma directa . Para anchura, una vez refuta toda la fórmula de L para cada cláusula , en anchura , por ejemplo, además de la anchura de la fórmula de L, y luego uno refuta la fórmula de L en la anchura . Suponiendo que ambas fórmulas tienen un ancho inicial constante, el ancho de la refutación de la suma directa será esencialmente . $A$ $B_i$ $w_A$ $B$ $B$ $w_B$ $\max (w_A, w_B)$

Por supuesto, esta es una observación fácil, pero el punto es que podría indicar que la pregunta sobre el espacio podría ser complicada. Esto es así ya que casi todos los límites inferiores en el espacio en refutación sabemos que van a través de límites inferiores de ancho. (Es decir, los límites inferiores del espacio se derivaron de forma independiente, pero en retrospectiva, todos siguen como un corolario del hermoso artículo "Una caracterización combinatoria del ancho de resolución" de Atserias y Dalmau). Pero si hay un teorema de suma directa para la cláusula de resolución espacio, no seguirá desde los límites inferiores de ancho, pero debe discutirse directamente, lo que al menos hasta ahora parece ser mucho más difícil. Pero, por supuesto, podría haber algún argumento fácil que me falta.

Jakob Nordstrom
fuente

Bienvenido Jakob!

arnab

Lamentablemente, los comentarios se limitan a personas con una reputación de al menos 50, lo cual es una rareza del software y se relaciona con la prevención de spam. Estoy seguro de que cruzarás ese umbral rápidamente.

Suresh Venkat

Hola Jakob, me alegro de verte aquí. (pd: creo que has pasado el umbral).

Kaveh

Hola Jakob, me pregunto si este tipo de declaración tiene algunas consecuencias con respecto a las compensaciones. Como una técnica de límite inferior que no sería una herramienta muy poderosa: la longitud de la fórmula se ajusta al cuadrado mientras que el espacio aumenta linealmente. De todos modos, esta propiedad podría conducir a una fórmula con un ancho pequeño y un espacio grande (tenga en cuenta que también el ancho aumenta si se realiza un número no constante de repetición).

MassimoLauria