Me he encontrado con el algoritmo polinómico que resuelve 2SAT. Me ha parecido sorprendente que 2SAT esté en P, donde todas (o muchas otras) de las instancias de SAT son NP-Complete. ¿Qué hace que este problema sea diferente? ¿Qué lo hace tan fácil (NL-Complete, incluso más fácil que...