Gostaria de saber o estado atual da transição de fase para k-sat aleatório, dadas n variáveis e cláusulas m, qual é o melhor conhecido c = m / n para os limites superior e inferior.
10
Gostaria de saber o estado atual da transição de fase para k-sat aleatório, dadas n variáveis e cláusulas m, qual é o melhor conhecido c = m / n para os limites superior e inferior.
Respostas:
Dimitris Achlioptas aborda isso em seu artigo de pesquisa do Handbook of Satisfiability ( PDF ).
Supõe-se que exista um único limiar para cada k ≥ 3 , de modo que quando m / n > r k , uma fórmula aleatória k -SAT com cláusulas m variáveis n seja insatisfatória com alta probabilidade e, portanto, quando m / n < r k , em seguida, uma aleatório m -clause, n -variável k fórmula -SAT pode ser satisfeita com alta probabilidade. (Mais precisamente, a conjectura é que no limite como nrk k ≥ 3 m / n > rk k m n m / n < rk m n k n tende ao infinito, a probabilidade de satisfação é 0 ou 1 nesses dois regimes, respectivamente.)
Supondo que essa conjectura de limiar de satisfação seja válida, os limites mais conhecidos para sãork
(esta tabela aparece na página indicada como 247 no rascunho).
Em um manuscrito mais recente (arXiv: 1411.0650 ), Jian Ding, Allan Sly e Nike Sun mostraram que, para todos os suficientemente grandes , existe de fato um limiar único r k = 2 k ln 2 - ( 1 + ln 2 ) / 2 + o ( 1 ) , e o termo de erro o ( 1 ) nesta expressão vai a zero, pois k tende ao infinito.k rk= 2kem2 - ( 1 + ln2 ) / 2+o(1) o ( 1 ) k
fonte