Uma característica bem conhecida das instâncias -SAT é a razão do número de cláusulas sobre o número de variáveis , ou seja, o quociente . Para cada , existe um valor limite st \ para , a maioria das instâncias é satisfatória e para maioria das instâncias não é satisfatória. Tem havido uma série de pesquisas feitas para problemas onde , e por problemas com suficientemente pequeno ,-SAT torna-se solucionável em tempo polinomial. Veja, por exemplo, o artigo de pesquisa de Dimitris Achlioptas do Handbook of Satisfiability ( PDF ).
Gostaria de saber se algum trabalho foi feito na outra direção (onde ), por exemplo, se podemos de alguma forma transformar o problema de CNF para DNF, neste caso, para resolvê-lo rapidamente.
Então, essencialmente, o que se sabe sobre SAT em que ?
fonte
Respostas:
Sim, houve. Moshe Vardi recentemente deu uma palestra de pesquisa no workshop BIRS Theoretical Foundations of Applied SAT Solving :
(Moshe apresenta o gráfico do experimento um pouco depois do minuto 14:30 em sua palestra acima.)
Seja a razão da cláusula. À medida que o valor de ρ aumenta além do limite, o problema se torna mais fácil para os solucionadores de SAT existentes, mas não tão fácil quanto era antes de atingir o limite. Há um aumento muito acentuado da dificuldade quando nos aproximamos do limiar a partir de baixo. Após o limiar, o problema se torna mais fácil comparado ao limiar, mas a diminuição da dificuldade é muito menos acentuada.ρ ρ
Seja denotado a dificuldade do problema em relação a n (no experimento T ρ ( n ) é o tempo médio de execução do GRASP em instâncias aleatórias do 3SAT com a razão de cláusulas ρ ). Moshe sugere que T ρ ( n ) muda da seguinte forma:Tρ(n) n Tρ(n) ρ Tρ(n)
fonte
Existem pelo menos duas linhas de pesquisa relativas a aleatório para fórmulas com uma razão de cláusula / variável maior que o limite de satisfação:k-SAT
fonte
Aqui está um estudo / ângulo mais antigo, mas relevante, de um especialista líder.
ele mostra o parâmetro estima o número de soluções e mede a "restrição" e correlaciona / tendências aproximadamente com a razão de cláusula para variável. veja p3 fig 4 em particularκ
a pergunta pergunta sobre . mas, a partir da análise empírica, isso é altamente confinado e, portanto, basicamente se aproxima de instâncias do tempo P (um solucionador "descobre" rapidamente que são insolúveis)) e, portanto, não é tão teórico quanto interessante (porque não "eliciam / exercitam" o tempo exponencial comportamento dos solucionadores em média). no entanto, pessoalmente, não vi trabalhos / transformações / teorias que provam isso mais teoricamente / rigorosamente (além deste artigo como um começo disso).m/n≫α
fonte