Um teorema de soma direta para a complexidade do espaço da cláusula Resolution?

A resolução é um esquema para provar a insatisfação dos CNFs. Uma prova na resolução é uma dedução lógica da cláusula vazia para as cláusulas iniciais do CNF. Em particular qualquer cláusula inicial pode ser inferida, e a partir de dois cláusulas $A \lor x$ e $B \lor \neg{x}$ a cláusula $A \lor B$ pode ser deduzida como bem. Uma refutação é uma sequência de deduções que termina com uma cláusula vazia.

Se essa refutação for implementada, podemos considerar um procedimento que mantém algumas cláusulas na memória. Caso uma cláusula não inicial precise ser usada novamente e não esteja mais na memória, o algoritmo deve fazê-lo novamente do zero ou daqueles na memória.

Deixe $Sp(F)$ o menor número de cláusulas a serem mantidas na memória para alcançar as cláusulas vazias. Isto é chamado o espaço cláusula complexidade da $F$ . Dizemos dizer que $Sp(F)=\infty$ é $F$ é satisfatório.

O problema que estou sugerindo é o seguinte: considere duas CNFs $A=\bigwedge_{i=1}^m A_i$ e $B=\bigwedge_{j=1}^n B_j$ , e deixar que o 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$

Qual é a relação de $Sp(A \lor B)$ com $Sp(A)$ e $Sp(B)$ ?

O limite superior óbvio é $Sp(A \lor B) \leq Sp(A) + Sp(B) -1$ . Isso é apertado?

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

Boa pergunta! Você sabe a resposta para o tamanho da soma direta? Eu acho que o pior caso é quando o A e o B não possuem variáveis compartilhadas. Um caso interessante pode ser quando A e B são iguais até a renomeação da variável. Aliás, não vejo como você consegue esse limite superior, parece que pode ser muito pior.

Kaveh

Agora vejo o limite superior, você pode copiar a refutação de

para

para obter

, um por um para cada

e depois fazer a refutação para

. O tamanho será em torno 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

Você está certo. Esqueci de mencionar isso, mas é claro que o caso mais interessante em termos de limite inferior é quando A e B não compartilham variáveis. Isso é exatamente o caso, eu estou realmente interessado. Considerando diferentes A e B é melhor indutivamente obter um resultado para

onde

são disjuntos cópias variáveis da mesma

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

Note-se que em relação comprimento refutação você facilmente ter

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

O limite superior do espaço trivial, na verdade, requer menos uma cláusula na memória. Eu editei de acordo.

MassimoLauria

Respostas:

Eu queria postar isso como um comentário, mas como não consigo descobrir o caminho, acho que terá que ser uma "resposta".

Eu concordo que a pergunta é boa. Obviamente, a mesma pergunta também pode ser feita sobre a duração das refutações de resolução (ou seja, o número de cláusulas que ocorrem na refutação, contadas com repetições) e a largura da refutação (ou seja, o tamanho ou o número de literais que ocorrem em , a maior cláusula da refutação).

Em todos esses casos, existem limites superiores "óbvios", mas não está claro para mim se é de esperar que os limites inferiores sejam iguais ou não. Portanto, eu queria adicionar uma pergunta e um comentário.

A questão diz respeito ao comprimento da refutação. Parece razoável acreditar que o limite de duração declarado no comentário de Massimo seja rígido, mas sabemos disso?

E o comentário diz respeito à largura. Observe que, para esta medida, um momento de reflexão revela que um limite inferior de soma direta não se mantém. Para largura, uma vez refuta toda a -Fórmula para cada cláusula , de largura , digamos, mais a largura do -Fórmula, e depois um refuta a -Fórmula de largura . Supondo que ambas as fórmulas tenham largura inicial constante, a largura da refutação da soma direta será essencialmente . $A$ $B_i$ $w_A$ $B$ $B$ $w_B$ $\max (w_A, w_B)$

É claro que é uma observação fácil, mas o ponto é que isso pode indicar que a questão do espaço pode ser complicada. Isso ocorre porque quase todos os limites inferiores no espaço em refutação que conhecemos passam por limites inferiores de largura. (Ou seja, os limites inferiores do espaço foram derivados independentemente, mas em retrospectiva todos eles seguem como corolário do belo artigo "Uma caracterização combinatória da largura da resolução" de Atserias e Dalmau.) Mas se existe um teorema da soma direta para a cláusula de resolução espaço, ele não segue da largura limites inferiores, mas deve ser discutido diretamente, o que pelo menos até agora parece ser muito mais difícil. Mas é claro que pode haver algum argumento fácil que estou perdendo.

Jakob Nordstrom
fonte

Bem-vindo, Jakob!

Arnab

Infelizmente, os comentários são limitados a pessoas com uma reputação de pelo menos 50 - isso é uma singularidade do software e está relacionado à prevenção de spam. Tenho certeza de que você cruzará esse limiar rapidamente.

precisa saber é o seguinte

Olá Jakob, é um prazer vê-lo aqui. (ps: Eu acho que você passou do limite.)

Kaveh

Olá Jakob, gostaria de saber se esse tipo de declaração tem algumas conseqüências em relação às compensações. Como uma técnica de limite inferior que não seria uma ferramenta muito poderosa: o comprimento da fórmula quadratura enquanto o espaço aumenta linearmente. De qualquer forma, essa propriedade pode levar à fórmula com largura pequena e espaço grande (observe que também a largura aumenta se um número não constante de repetição for feito).

MassimoLauria 17/01