Können Sie die Äquivalenz für monotone Boolesche Ausdrücke festlegen, die in PTIME keine Negation enthalten?

16

Liegt das folgende Problem in PTIME oder coNP-hard vor:

Bei zwei booleschen Ausdrücken und in den Variablen ohne Negation (dh die Ausdrücke werden vollständig über und ). Entscheiden Sie, ob , für alle Zuordnungen zu den Variablen den gleichen Wert haben.e1e2x1,,xne1e2

Wenn beide Ausdrücke in DNF angegeben würden, liegt das Problem in PTIME, da wir zuerst die Konjunktivsätze lexikografisch ordnen und vergleichen könnten. Das Bringen eines beliebigen Ausdrucks zu DNF kann jedoch exponentiell explodieren. Ein ähnliches Argument scheint für binäre Entscheidungsdiagramme zu gelten.

Offensichtlich liegt das Problem bei coNP.

Ich habe ziemlich viel gegoogelt, aber keine Antwort gefunden.

Entschuldigung für die elementare Frage.

Danielzinn
quelle

Antworten:

14

Korollar 3.5 von [BHR84] zeigt, dass das Problem coNP-vollständig ist.

[BHR84] PA Bloniarz, HB Hunt, III und DJ Rosenkrantz. Algebraische Strukturen mit harten Äquivalenz- und Minimierungsproblemen. Journal of the ACM , 31 (4): 879–904, Okt. 1984. http://dx.doi.org/10.1145/1634.1639

Tsuyoshi Ito
quelle