Ponente
Descripción
El estudio de los problemas para los que no se ha encontrado una solución de complejidad polinomial (NP) es de suma importancia para la ciencia contemporánea. El problema Random 3-Satisfaction (3-SAT) es el primer problema en ser clasificado como NP-completo, cuya complejidad es cota superior de cualquier problema NP. En este trabajo proponemos un método numérico y otro semi-analítico para determinar qué instancias del problema 3-SAT son solubles usando el Simulated Annealing. Este es uno de los algoritmos más importantes de la Física Estadística aplicados a resolver problemas de optimización. Nuestra descripión semi-analítica del algoritmo utiliza una aproximación de cavidad para resolver la Ecuación Maestra del proceso que define el Simulated
sobre el 3-SAT.
