Los detalles de la pregunta indican que
parece extraño que se le presente un circuito booleano aleatorio y se le pregunte si se puede satisfacer
El objetivo de resolver SAT generalmente no es resolver circuitos booleanos aleatorios , sino resolver circuitos booleanos altamente estructurados . Puede codificar cualquier función computable en circuitos booleanos. (Después de todo, el procesador de su computadora es principalmente un grupo de circuitos booleanos).
- ¿Qué temas matemáticos recomiendas en informática?
- ¿Cómo los operadores matemáticos mapean objetos de un punto a otro en el espacio?
- ¿Es un cierre una función o el entorno en el que se definió dicha función?
- ¿Cuál es el alcance de la probabilidad y las matemáticas discretas en ciencias de la computación?
- ¿Cuál es la complejidad temporal para ordenar n cadenas de n caracteres, cada una utilizando un orden lexicográfico?
Por ejemplo, digamos que quería factorizar un número entero, n . Puedo escribir un circuito booleano que, tomando como entrada un par de enteros ( p, q ) en binario, comprueba si pq = n. ¡Ahora, encontrar una entrada satisfactoria para ese circuito es lo mismo que factorizar n ! Como puede ver, la capacidad de resolver SAT sería enormemente poderosa.
Intuitivamente, si cada vez que escuchas “circuito booleano pequeño” piensas “función computable eficientemente”, entonces es más fácil entender por qué resolver SAT es tan “universal”.
Supongo que uno podría discutir lo mismo sobre cualquier otro problema NP-completo, pero SAT de alguna manera se ha convertido en el canónico. Supongo que esto se debe a que es mucho más fácil escribir su función como un circuito booleano que escribirla como, por ejemplo, una instancia de problema de camarilla máxima.
