Hola, manooooh.
La conversión a FND de una fórmula cualquiera puede tener un número de pasos que depende exponencialmente de la cantidad de literales (no de variables) que tenga. Por lo que en cuanto a eficiencia, puede ser un método aún más costoso que el de las tablas de verdad (que es exponencial respecto de las variables).
Pero creo haber hallado una forma de hacerlo, que aparentemente es de orden lineal o polinómico. O por lo menos es más divertido!
Se trata de dibujar la fórmula como viene, sin conversión alguna, en un circuito de cables. No el de compuertas electrónicas que resulta un laberinto muy poco intuitivo. Adjunto un gráfico.

Teniendo ese gráfico, cada camino entre el inicio (círculo verde) y el final (triángulo rojo) es una cláusula disyuntiva. Y es muy fácil encontrar visualmente si una fórmula es consistente o no. En el ejemplo, se ve que es consistente, con dos combinaciones (caminos) posibles.
Si negamos la última aparición de la variable X2, vemos muy fácilmente que es inconsistente.
Estoy intentando hacer un programa que use este método, pero sin pasar por la conversión a grafo. Simplemente la forma de leer los literales está dada por los símbolos de agrupación y por lo operadores lógicos.
Para dar una idea, si tenemos la fórmula en un arreglo de caracteres, podemos ir trazando los caminos teniendo en cuenta que por cada grupo disyuntivo hay tantos caminos como literales. Se toma un literal, se lo elimina del arreglo, y se pasa al final del grupo disyuntivo, hasta encontrar otro grupo, y así sucesivamente.
Todavía tengo que ver si este algoritmo sería exponencial o no.
Si alguien tiene interés en desarrollar ese programa, podemos colaborar. Creo que tiene muchas aplicaciones al diseño de los circuitos electrónicos, y también interesantes usos pedagógicos. Yo lo he comprobado incluso con niños de primaria, entre 6 y 11 años. Los caminos son intuitivos, no hay mucho que explicar, y las variables son puentes levadizos: afirmada, el puente está accesible; negada, el puente está levantado y no hay camino por allí. Incluso se podría pensar como un juego, con animación gráfica. No es complejo, pero sí muy laborioso, y solo no tengo ánimos.
En este artículo:
https://www.academia.edu/s/da61caba7e/linear-sat-decider-np-completeness-in-question?source=link...trato el tema, junto a otros relacionados.
Saludos