El problema de SAT pertenece a NP dado que puede ser resuelto con una máquina de Turing no determinista que genere todas las posibles combinaciones de valores para las variables de la expresión y, en forma no determinista, intente verificar si alguna de ellas hace que la expresión se evalúe en verdadero, en cuyo caso acepta la entrada.