¿Cuáles son los límites superiores e inferiores más conocidos actuales en el umbral de (des) satisfacción para aleatorio k-sat y / o 3-sat?

10

Me gustaría saber el estado actual de la transición de fase para k-sat aleatorio, dadas n variables y m cláusulas, cuál es la c = m / n más conocida para los límites superior e inferior.

Tayfun Pay
fuente
2
¿Intentaste una búsqueda de referencia? cf. meta.cstheory.stackexchange.com/questions/300/…
RJK
3
PD: Me parece que el segundo éxito en Google es un artículo de acceso libre con respuestas a su pregunta. (Un artículo arXiv de 2009 de Coja-Oghlan.)
RJK
Visite cstheory.stackexchange.com/questions/1130/… para obtener una perspectiva razonablemente actualizada. Los seguimientos de las personas que trabajan en esta área, como Amin Coja-Oghlan y Dimitris Achlioptas, tienen la respuesta que está buscando.
András Salamon
Todavía no he recibido una respuesta definitiva. Apreciaré si alguien me puede dar una respuesta definitiva. Gracias
Tayfun Pay
Puede encontrar esta pregunta útil: cstheory.stackexchange.com/questions/2168/… . En particular, vea la primera respuesta.
Giorgio Camerani

Respuestas:

17

Dimitris Achlioptas cubre esto en su artículo de la encuesta del Manual de Satisfabilidad ( PDF ).

Se conjetura que hay un umbral único para cada k 3 , de modo que cuando m / n > r k, entonces una fórmula aleatoria k -SAT con m cláusulas yn variables no es satisfactoria con alta probabilidad, y cuando m / n < r k entonces un azar m -clause, n -Variable k fórmula -SAT es satisfiable con alta probabilidad. (Más precisamente, la conjetura es que en el límite como nrkk3metro/ /norte>rkkmetronortemetro/ /norte<rkmetronorteknorte tiende al infinito, la probabilidad de satisfacción es 0 o 1 en estos dos regímenes, respectivamente).

Suponiendo que se cumple esta Conjetura del umbral de satisfacción, los límites más conocidos para sonrk

k 3 4 5 7 10 20
Mejor límite superior 4.51 10.23 21.33 87.88 708.94 726,817
Mejor límite inferior 3.52 7.91 18.79 84.82 704.94 726,809

(esta tabla aparece en la página indicada como 247 en el borrador).

En un manuscrito más reciente (arXiv: 1411.0650 ), Jian Ding, Allan Sly y Nike Sun mostraron que para todos los suficientemente grandes , de hecho, hay un umbral único r k = 2 k ln 2 - ( 1 + ln 2 ) / 2 + o ( 1 ) , y el término de error o ( 1 ) en esta expresión va a cero cuando k tiende al infinito.krk=2kEn2-(1+En2)/ /2+o(1)o(1)k

András Salamon
fuente