¿Puedes decidir la equivalencia para expresiones booleanas monótonas que no contienen negación en PTIME?

16

¿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 1e 2 , es decir, tienen el mismo valor para todas las asignaciones a las variables.mi1mi2X1,...,Xnortemi1mi2

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.

danielzinn
fuente

Respuestas:

14

El corolario 3.5 de [BHR84] muestra que el problema está completo.

[BHR84] PA Bloniarz, HB Hunt, III y DJ Rosenkrantz. Estructuras algebraicas con problemas de equivalencia y minimización. Journal of the ACM , 31 (4): 879–904, octubre de 1984. http://dx.doi.org/10.1145/1634.1639

Tsuyoshi Ito
fuente