Quantas tautologias existem?

17

Dado , quantos NDFs com variáveis ​​e cláusulas são tautologia? (ou quantos CNFs são insatisfatórios?)k n m km,n,kknmk

Anônimo
fonte
9
Um pouco de motivação nos ajudaria a acreditar que essa não é apenas uma pergunta aleatória.
Andrej Bauer 19/11
11
@AndrejBauer: Eu estava lendo sobre os solucionadores de SAT e seu desempenho.
Anônimo

Respostas:

29

A resposta depende k , m , e n . As contagens exatas geralmente não são conhecidas, mas existe um fenômeno de "limite" que, para a maioria das configurações de k , m , n , quase todas as instâncias de k SAT são satisfatórias ou quase todas as instâncias são insatisfatórias. Por exemplo, quando k=3 , tem-se, empiricamente, que, quando m<4.27n , todos menos um o(1) fracção de 3-SAT casos são satisfeita, e quando m>4.27n , mas sim um fração é insatisfatória. (Também são conhecidas provas rigorosas dos limites.)o(1)

Um ponto de partida é "A ordem assintótica do limiar de k-SAT" .

Amin Coja-Oghlan também trabalhou muito nesses problemas de limiar de satisfação.

Ryan Williams
fonte
5

Este é um comentário estendido para complementar a resposta de Ryan, que trata dos limites em que o número de cláusulas se torna grande o suficiente para que a instância seja quase certamente insatisfatória. Pode-se também calcular os limites muito maiores em que o número de cláusulas força a insatisfação quando excede a função de .n

Observe que alguns problemas técnicos precisam ser resolvidos. Se cláusulas repetidas são contadas em , então m pode ser tão grande quanto desejado, sem alterar n . Isso destruiria a maioria dos relacionamentos entre m e n . Portanto, assuma que m é o número de cláusulas distintas. Precisamos decidir sobre outro detalhe, se as instâncias são codificadas para que a ordem dos literais em uma cláusula ou a ordem das cláusulas em uma instância importem. Suponha que isso não seja importante, portanto, duas instâncias são consideradas equivalentes se contiverem as mesmas cláusulas e duas cláusulas são equivalentes se contiverem os mesmos literais. Com essas suposições, podemos agora limitar o número de cláusulas distintas que podem ser expressas commmnmnm variáveis. Cada cláusula pode ter cada variável ocorrendo positiva ou negativamente, ou de modo algum, e então m 3 n .nm3n

Primeiro, considere SAT sem restrição sobre . Qual é o maior m tal que a instância é satisfatória? Sem perda de generalidade, podemos supor que a atribuição de zero é uma solução. Existem então 3 n - 2 n cláusulas diferentes consistentes com esta solução, cada uma contendo pelo menos um literal negado. Portanto, m 3 n - 2 n para qualquer instância satisfatória. A instância que consiste em todas as cláusulas em que cada uma contém pelo menos um literal negado possui muitas cláusulas e é satisfeita pela atribuição zero. Além disso, pelo princípio do pigeonhole, qualquer instância com pelo menos 3 nkm3n-2nm3n-2n cláusulas não são satisfatórias.3n-2n+1 1

Isso produz subconjuntos diferentes de tais cláusulas, cada um representando uma instância distinta que é satisfeita por alguma atribuição. Em comparação, o número total de instâncias diferentes é 2 3 n .23n-2n23n

Agora modificando o acima para os casos em que cada cláusula tem no máximo literais, existem Σ k i = 0 ( nkdistingue tais cláusulas e k i = 0 ( nEu=0 0k(nEu)2Eu cláusulas em que não há literais negativos, entãomΣ k i = 0 ( nEu=0 0k(nEu)para instâncias satisfatórias, e qualquermmaioré insatisfatório. Existem então2 k i = 0 ( nmEu=0 0k(nEu)(2Eu-1 1)minstâncias satisfeitas por uma determinada tarefa, do total de2 k i = 0 ( n2Eu=0 0k(nEu)(2Eu-1 1)k-SAT instâncias.2Eu=0 0k(nEu)2Eu k

András Salamon
fonte
11
Eu também produzi o mesmo resultado em 2008 ish. Também existem funções complementares para literais e variáveis, de modo que, se você não assume repetição de literais, variáveis ​​ou cláusulas, se mais de x muitos ou y muitos literais ou variáveis ​​ocorrerem respectivamente, a instância fornecida não é satisfatória. Eu teria que cavar para encontrar essas duas funções. 1
Tayfun Pay