Quais são os limites superior e inferior mais conhecidos atualmente no limiar de (in) satisfação para k-sat aleatório e / ou 3-sat?

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.

Tayfun Pay
fonte
2
Você tentou uma pesquisa de referência? cf. meta.cstheory.stackexchange.com/questions/300/…
RJK
3
PS Parece-me que o segundo hit no Google é um artigo de acesso livre com respostas para sua pergunta. (Um artigo do arXiv de 2009 por Coja-Oghlan.)
RJK
Consulte cstheory.stackexchange.com/questions/1130/… para obter uma perspectiva razoavelmente atualizada. Os acompanhamentos das pessoas que trabalham nesta área, como Amin Coja-Oghlan e Dimitris Achlioptas, têm a resposta que você está procurando.
András Salamon
Ainda não recebi uma resposta definitiva. Agradeço se alguém puder me dar uma resposta definitiva. Obrigado
Tayfun Pay
Você pode achar essa pergunta útil: cstheory.stackexchange.com/questions/2168/… . Em particular, veja a primeira resposta.
Giorgio Camerani 25/10/10

Respostas:

17

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 nrkk3m/n>rkkmnm/n<rkmnkn 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

k 3 4 5 7 10 20
Melhor limite superior 4,51 10,23 21,33 87,88 708,94 726.817
Melhor limite inferior 3,52 7,91 18,79 84,82 704,94 726.809

(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.krk=2kem2-(1 1+em2)/2+o(1 1)o(1 1)k

András Salamon
fonte