Tengo una fórmula booleana: (x_ {1} o x_ {2}) y (x_ {3} o x_ {4}) y ..... y (x_ {2r-1 } o x_ {2r}), donde x_ {i} pertenece al conjunto: {p_ {1}, p_ {2}, ... p_ {99}, ~ p_ {1}, ~ p_ { 2}, ... ~ p_ {99}} y tengo que determinar si para algunos valores de x_ {i} la fórmula dada puede ser verdadera.Satisfabilidad booleana - algoritmo
Sé que es en general computacionalmente difícil. Pero, ¿hay alguna forma bastante rápida de poder resolver este problema en particular? Hasta ahora he intentado retroceder, es decir, en recursividad, sustituyo cada valor posible (0 o 1, por lo tanto, no muchos) por cada variable posible, y cada variable, que aún no tiene valor, es trivialmente cierta. Antes de profundizar en la recursividad, comparto la fórmula (incluso cuando no todas las variables tienen un valor) y si es falsa, no profundizo. Pero es muy lento. ¿Algunas ideas? Estaría muy agradecido por la ayuda.
Parece un problema interesante, pero quizás [Math.StackExchange] (http://math.stackexchange.com/) podría ayudarlo más con el desarrollo de algoritmos. Sin embargo, ¡te ayudaremos a implementarlo! –