Apakah masalah berikut di PTIME, atau coNP-hard:
Diberikan dua ekspresi Boolean dan dalam variabel , tanpa negasi (yaitu, ekspresi sepenuhnya dibangun melalui dan ). Putuskan apakah , yaitu mereka memiliki nilai yang sama untuk semua tugas ke variabel.e 2 x 1 , ... , x n ∧ ∨ e 1 ≡ e 2
Jika kedua ekspresi akan diberikan dalam DNF, maka masalahnya ada di PTIME karena kita dapat memesan leksikografis klausa konjungtif dan membandingkannya terlebih dahulu. Tetapi membawa ekspresi sewenang-wenang ke DNF dapat meledak secara eksponensial. Argumen serupa tampaknya berlaku untuk diagram keputusan-biner.
Jelas, masalahnya ada di TNP.
Saya mencari-cari dalam jumlah yang wajar, tetapi tidak dapat menemukan jawaban.
Permintaan maaf untuk pertanyaan dasar.