Czy następujący problem występuje w trybie PTIME lub coNP-hard:
Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennych , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań do zmiennych.
Jeśli oba wyrażenia byłyby podane w DNF, to problem występuje w PTIME, ponieważ moglibyśmy najpierw leksykograficznie uporządkować zdania spójne i porównać. Ale wprowadzenie arbitralnego wyrażenia do DNF może wybuchnąć wykładniczo. Podobny argument wydaje się dotyczyć diagramów decyzji binarnych.
Oczywiście problem dotyczy coNP.
Szukałem w Google w sporej ilości, ale nie mogłem znaleźć żadnej odpowiedzi.
Przepraszamy za podstawowe pytanie.