¿Es el siguiente problema en PTIME o coNP-hard:
Dadas dos expresiones booleanas y e 2 en variables x 1 , ... , x n , sin negación (es decir, las expresiones se construyen completamente a través de ∧ y ∨ ). Decida si e 1 ≡ e 2 , es decir, tienen el mismo valor para todas las asignaciones a las variables.
Si ambas expresiones se darían en DNF, entonces el problema está en PTIME ya que primero podríamos ordenar lexicográficamente las cláusulas conjuntivas y compararlas. Pero traer una expresión arbitraria a DNF puede explotar exponencialmente. Un argumento similar parece ser válido para los diagramas de decisión binarios.
Obviamente, el problema está en coNP.
Estaba buscando en Google bastante, pero no pude encontrar ninguna respuesta.
Disculpas por la pregunta primaria.