Você pode decidir a equivalência para expressões booleanas monótonas que não contêm negação em PTIME?

O problema a seguir é PTIME ou coNP-hard:

Dadas duas expressões booleanas e e 2 nas variáveis x 1 , … , x n , sem negação (ou seja, as expressões são totalmente construídas via ∧ e ∨ ). Decida se e 1 ≡ e 2 , ou seja, eles têm o mesmo valor para todas as atribuições às variáveis.$e_1$$e_2$$x_1,\dots,x_n$$\wedge$$\vee$$e_1 \equiv e_2$

Se ambas as expressões forem dadas no DNF, o problema estará no PTIME, pois poderíamos primeiro lexicograficamente ordenar as cláusulas conjuntivas e comparar. Mas trazer uma expressão arbitrária para o DNF pode explodir exponencialmente. Um argumento semelhante parece valer para diagramas de decisão binária.

Obviamente, o problema está no coNP.

Pesquisei bastante no Google, mas não consegui encontrar resposta.

Desculpas pela questão elementar.

O corolário 3.5 de [BHR84] mostra que o problema está coNP-completo.

[BHR84] PA Bloniarz, HB Hunt, III e DJ Rosenkrantz. Estruturas algébricas com equivalência rígida e problemas de minimização. Journal of the ACM , 31 (4): 879–904, outubro de 1984. http://dx.doi.org/10.1145/1634.1639