Imagine que tiene un montón de interruptores frente a usted, cada uno de los cuales puede estar arriba o abajo.
Imagine que también tiene un montón de bombillas, cada una de las cuales está controlada por unos pocos (por ejemplo, tres) interruptores. La quinta bombilla podría encenderse si alguno de los interruptores tercero, 13 o 33 está encendido, o la séptima bombilla podría encenderse si el segundo interruptor está arriba y / o el tercer interruptor está abajo.
El problema de la satisfacción booleana (SAT) es encontrar una manera, examinando el cableado entre los interruptores y las bombillas, para saber si hay alguna configuración de interruptores de manera que todas las bombillas se enciendan más rápido que simplemente probar todas las configuraciones posibles del interruptor .
- ¿Qué computadoras portátiles son más adecuadas para los estudiantes de CS?
- ¿Cómo se beneficiaría el mundo de la inteligencia artificial?
- Mientras se detectan fallas en los sistemas distribuidos, ¿cuándo es una solución mejor que las encuestas?
- Cómo mejorar en el aprendizaje automático
- ¿Qué debería preferir: CSE en IIT-G o IIT-BHU o IIT-H?
Probar todas las combinaciones de interruptores es “lento” porque el número de combinaciones posibles aumenta rápidamente con el número de interruptores: para 2 interruptores, hay 4 combinaciones; para 3, hay 8; para 10, hay alrededor de 1000; para 20, hay alrededor de un millón. Para 333 interruptores, hay más de un googol ([matemática] 10 ^ {100} [/ matemática]), más que el número de partículas en el universo.
El problema es importante porque pertenece a una clase de problemas llamados problemas “NP”. Los problemas de NP tienen la propiedad de saber rápidamente si una solución determinada funciona (en este caso, puede verificar si una configuración determinada de conmutadores funciona configurándolos y mirando para ver si es correcta), pero no se sabe Cómo encontrar una solución rápidamente.
Otro problema de NP es el problema del vendedor ambulante, dado un conjunto de ciudades y las distancias entre ellas, ¿es posible que un vendedor visite cada ciudad una vez y regrese a casa mientras viaja a menos de una distancia especificada? Dada una ruta, puede verificar fácilmente que cumple con los criterios, pero es difícil encontrar una ruta.
SAT (and Travelling Salesman) es parte de un subconjunto más pequeño de problemas de NP llamado “NP-Complete”, que tiene la propiedad adicional de que cualquier instancia de un problema de NP se puede convertir en una instancia de un problema de NP-Complete de tal manera que resolver El problema NP-Complete puede ayudarlo a resolver rápidamente el problema NP original.
Puede “codificar” ingeniosamente un problema de vendedor ambulante en un cableado de un grupo de interruptores y bombillas para obtener un problema SAT, y resolver el problema SAT (¿hay una configuración de interruptor que encienda todas las bombillas?) Resolverá el vendedor ambulante problema (¿puede el vendedor completar su ruta y llegar a casa sin poner demasiadas millas en su automóvil?).
Hay muchos problemas de NP-Complete, y descubrir cómo resolver cualquiera de ellos rápidamente le permitirá resolverlos rápidamente.
