El problema de k-SAT en n variables sería determinar si existe una interpretación de todas las n variables lógicas distintas para satisfacer la fórmula dada en forma conjuntiva normal.
Se sabe que el problema 3-SAT es NP-Complete. Sin embargo, cuando establece k = 1, la expresión booleana que necesitamos satisfacer se reduce a las variables lógicas AND-ed juntas. Puedo pensar en una solución de tiempo polinomial trivial para esto, donde escanea la expresión y almacena las variables encontradas en una tabla hash (una matriz sería suficiente). Para todas las variables lógicas, si aparece alguna en la expresión junto con su negación, entonces obviamente la fórmula no es satisfactoria. De lo contrario lo es.
Notas adicionales:
- Cómo convertir 25 cm a mm sin usar una regla
- ¿Cómo se puede construir un nuevo generador de números pseudoaleatorios criptográficamente útil?
- ¿Cómo podemos convertir una imagen en un sistema binario (0 y 1) o un código como QR?
- ¿Qué hace que la oración 'Lucas no pueda afirmar esta oración constantemente', vulnerable o incluso incompleta?
- ¿Es posible iterar a través de todos los números reales en [a, b] en cualquier lenguaje de programación? ¿Se acerca algo?
Entonces, ahora sabemos que existe un algoritmo de tiempo polinómico para 1-SAT, si puede reducir cualquier problema NP-Complete a este problema, entonces toda la clase colapsaría, dando P = NP (que la mayoría de la comunidad CS piensa es poco probable)
El problema 2-SAT también se encuentra en P junto con el 1-SAT. Para cualquier k> 2, el problema k-SAT es NP-Completo.
