Estoy interesado en la densidad 3 satisfacciones críticas (3-SAT) . Se conjetura que tal existe: si el número de cláusulas 3-SAT generadas al azar es más, es casi seguro que no son satisfactorias. (Aquí es cualquier constante pequeña es el número de variables). Si el número es o menos, es casi seguro que son satisfactorias.
La tesis Algoritmos de propagación de creencias para problemas de satisfacción de restricciones de Elitza Nikolaeva Maneva desafía el problema desde el ángulo de propagación de creencias conocido en la teoría de la información. En la página 13, dice si existe .
¿Cuáles son los límites más conocidos para ?
Respuestas:
A pesar del teorema de Friedgut sobre -SAT, aunque carecemos de técnicas para llegar a insignificante para pequeña , parece más útil hablar sobre el umbral de satisfacción ( ) y el umbral de insatisfacción ( ) como entidades separadas.k ϵ k α−ϵ α+ϵ
Se sabe que el umbral de insatisfacción es como máximo 4.4898, una ligera mejora desde la tesis de Maneva de 2001.
Se sabe que el umbral de satisfacción es al menos 3.52, que no ha cambiado desde el momento de la tesis de Maneva.
Achlioptas y Menchaca-Méndez citaron recientemente estos límites como los más conocidos hasta la fecha.
fuente
Hay un nuevo documento de 58 páginas (32 referencias) aceptado para STOC 2013,
que examina y avanza el área de determinación del umbral preciso de k-SAT, especialmente a partir de resultados tomados de la física estadística. Del resumen:
Coja-Oghlan, Amin; Panagiotou, Konstantinos , Tras el umbral de -SATk , Actas del 45º simposio anual de ACM sobre teoría de la informática, STOC '13. Palo Alto, CA, EE. UU., Del 1 al 4 de junio de 2013. Nueva York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 705-714 (2013). ZBL1293.68164 .
fuente