Limites mais estreitos de corrente para densidade crítica de 3-SAT

26

Estou interessado na densidade crítica de 3-satisfação (3-SAT) . É suposto que tal exista: se o número de cláusulas 3-SAT geradas aleatoriamente for ou mais, elas são quase certamente insatisfatórias. (Aqui é qualquer constante pequena e é o número de variáveis.) Se o número for ou menos, elas são quase certamente satisfatórias.αα(α+ϵ)nϵn(αϵ)n

Os algoritmos de tese de propagação de crenças para problemas de satisfação de restrições de Elitza Nikolaeva Maneva desafiam o problema do ângulo de propagação de crenças conhecido na teoria da informação. Na página 13, diz se existir.3.52<α<4.51α

Quais são os limites mais conhecidos para ?α

Jun
fonte
1
Ver também questão cstheory.stackexchange.com/q/1130
András Salamon

Respostas:

17

Não obstante o teorema de Friedgut sobre -SAT, enquanto que nos falta técnicas para chegar ao insignificante ε para pequenas k , parece mais útil para falar sobre o limiar satisfiability ( α - ε ) eo limiar unsatisfiability ( α + ε ) como entidades separadas.kϵkαϵα+ϵ

Sabe-se que o limiar de insatisfação é no máximo 4.4898, uma ligeira melhora desde a tese de Maneva em 2001.

Sabe-se que o limiar de satisfação é pelo menos 3,52, inalterado desde a tese de Maneva.

  • AC Kaporis, LM Kirousis, EG Lalas. A análise probabilística de um algoritmo de satisfação ganancioso , estruturas aleatórias e algoritmos 28 , 2006, 444-480. doi: 10.1002 / rsa.20104

Esses limites foram recentemente citados por Achlioptas e Menchaca-Mendez como os mais conhecidos até o momento.

  • D. Achlioptas, R. Menchaca-Mendez. Limites de insatisfação para CSPs aleatórios de um método de interpolação energética , ICALP 2012, LNCS 7391, 1–12. doi: 10.1007 / 978-3-642-31594-7_1
András Salamon
fonte
6

Há um novo documento de 58 páginas (32 refs) aceito no STOC 2013,

Seguindo o limiar de k-SAT por Coja-Oghlan e Konstantinos Panagiotou

que pesquisa e avança na área de determinação do limiar de k-SAT preciso, construindo especialmente a partir de resultados emprestados da física estatística. Do resumo:

Aqui, desenvolvemos um novo método assimétrico de segundo momento que nos permite abordar esse problema pela primeira vez na teoria dos CSPs aleatórios. Essa técnica permite calcular o limite de k-SAT até um aditivo em2-12+O(1/k)0,19.

k

vzn
fonte