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

16

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 1e 2 , ou seja, eles têm o mesmo valor para todas as atribuições às variáveis.e1 1e2x1 1,...,xne1 1e2

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.

danielzinn
fonte

Respostas:

14

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

Tsuyoshi Ito
fonte