Apa kompleksitas masalah kesetaraan untuk pohon keputusan baca-sekali?

Pohon keputusan baca-sekali didefinisikan sebagai berikut:

dan -baca sekali pohon keputusan. $True$ $False$
Jika dan adalah pohon keputusan baca-sekali dan adalah variabel yang tidak terjadi di dan , maka juga merupakan pohon keputusan baca-sekali. $A$ $B$ $x$ $A$ $B$ $(x \land A) \lor (\bar x \land B)$

Input: Dua baca-sekali pohon keputusan dan . $A$ $B$
Output: Apakah ? $A \equiv B$

Motivasi:

Masalah ini muncul ketika saya melihat masalah kesetaraan bukti (permutasi aturan) dari sebuah fragmen Linear Logic.

cc.complexity-theory lo.logic decision-trees boolean-formulas Marc
sumber

Tidak bisakah Anda menggunakan diagram keputusan biner yang diperkecil? Sunting: err mungkin tidak, variabel Anda tidak dipesan ...

Sylvain

@ Kaveh Tidak, itu terjadi dalam teori bukti: Saya melihat masalah kesetaraan bukti (permutasi aturan) dari sebuah fragmen Logika Linear. Intinya adalah masalah boolean ini. Karena saya bukan spesialis, saya pikir saya akan bertanya apakah ini pertanyaan yang mudah diketahui / mudah. Karenanya, ya saya mengarang nama itu karena saya tidak tahu apa-apa.

Marc

@ Mark, umumnya ide yang bagus untuk menjelaskan mengapa Anda tertarik pada masalah. Saya mengedit pertanyaan. Silakan lihat untuk memastikan itu baik-baik saja. (Juga menghapus komentar saya sebelumnya karena tidak diperlukan lagi.)

Kaveh

@ Kaveh Ya, maaf soal itu. Saya mengedit reformulasi Anda untuk membuatnya lebih dekat dengan argumen asli saya (saya tidak dapat segera mengetahui apakah Anda baik-baik saja sehingga tampaknya lebih mudah untuk melakukan ini)

Marc

Jawaban:

Saya menemukan solusi parsial. Masalahnya adalah di L.

Negasi dari setara dengan yang setara dengan IFF baik dan adalah. $A \leftrightarrow B$ $(\bar A \land B) \lor (A \land \bar{B})$ $False$ $(\bar A \land B)$ $(A \land \bar{B})$

Membaca-sekali pohon keputusan untuk dapat diperoleh dari pohon keputusan read-sekali untuk dengan beralih dan di . Ini bisa dilakukan di ruang log. $\bar{A}$ $A$ $True$ $False$ $A$

$\bar A \land B$ $False$ ${A} \land \bar{B}$ $True$ $x$ $\bar x$ $False$

Jadi masalahnya setidaknya di L.

$AC_0$

EDIT2: itu dia, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

Jadi masalahnya memang Logspace-complete.

Marc
sumber

x . A + \bar{x} . B

$x.A+\overline{x}.B$

(\bar{x} + \bar{A}) . (x + \bar{B})

$(\overline{x}+\overline{A}).(x+\overline{B})$

x . \bar{A} + \bar{x} . \bar{B} + \bar{A} . \bar{B}

$x.\overline{A}+\overline{x}.\overline{B}+\overline{A}.\overline{B}$

x . \bar{A} + \bar{x} . \bar{B}

$x.\bar A+\bar x.\bar B$

x

$x$

\bar{x}

$\overline{x}$

1

$1$

L

$L$

Cara yang lebih mudah untuk menyatakan ini adalah: Setiap jalur adalah istilah minimum atau maksimum tergantung pada label daunnya. Kami memeriksa apakah mereka memiliki ketentuan min yang sama. Kami dapat menghitung min-term dalam ruang log dan memeriksa apakah dua min-term yang sama adalah dalam ruang log.

Kaveh

N C^{1}

$NC^1$

A C^{0}

$AC^0$

A C^{0}

$AC^0$

$\phi$

$0$ $1$ $1$ $\{x,\overline{y},z\}$ $\{x,\overline{y},z\}$ $\{x,y,z\}$ $\{x,z\}$ $y$ $\{x,\overline{y},z,t\}$ $\{x,y,z\}$

$\{x_1,\dots,x_n\}$ $i$ $x_i$ $\{\vec x,x_i,x_j\},\{\vec x,\overline{x_j}\}$ $\{\vec x,x_i\},\{\vec x,\overline{x_i},\overline{x_j}\}$ $i<j$ $\vec x$ $x_i$ $x_j$ $j-i$

$P$

Denis
sumber

x, y, z

$x,y,z$

x, \bar{y}, z

$x,\bar y,z$

x, y, \bar{z}

$x,y,\bar z$

Ah ya lupa itu, saya menambahkan perbaikan berharap itu berfungsi sekarang.

Denis

Jangan lupa untuk mengklaim $ juta Anda jika berhasil :)

Marc

L

$L$