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.
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.