Dado , quantos NDFs com variáveis e cláusulas são tautologia? (ou quantos CNFs são insatisfatórios?)k n m k
co.combinatorics
lo.logic
sat
Anônimo
fonte
fonte
Respostas:
A resposta dependek , 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.
fonte
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 comm m n m n m variáveis. Cada cláusula pode ter cada variável ocorrendo positiva ou negativamente, ou de modo algum, e então m ≤ 3 n .n m ≤ 3n
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 nk m 3n- 2n m ≤ 3n- 2n cláusulas não são satisfatórias.3n- 2n+ 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- 2n 23n
Agora modificando o acima para os casos em que cada cláusula tem no máximo literais, existem Σ k i = 0 ( nk distingue tais cláusulas e∑ k i = 0 ( n∑ki = 0( nEu) 2Eu cláusulas em que não há literais negativos, entãom≤Σ k i = 0 ( n∑ki = 0( nEu) para instâncias satisfatórias, e qualquermmaioré insatisfatório. Existem então2∑ k i = 0 ( nm ≤ ∑ki = 0( nEu) (2Eu- 1 ) m instâncias satisfeitas por uma determinada tarefa, do total de2∑ k i = 0 ( n2∑ki = 0( nEu) (2Eu- 1 ) k-SAT instâncias.2∑ki = 0( nEu) 2Eu k
fonte