Какова сложность проблемы эквивалентности для деревьев решений с однократным чтением?

Дерево решений однократного чтения определяется следующим образом:

и считываются однократно деревьев решений. $True$ $False$
Если и являются деревьями решений с однократным чтением, а является переменной, не встречающейся в и , то также является деревом решений с однократным чтением. $A$ $B$ $x$ $A$ $B$ $(x \land A) \lor (\bar x \land B)$

Входные данные : Два чтения один раз деревьев решений и . $A$ $B$
Выход: ? $A \equiv B$

Мотивация:

Эта проблема возникла, когда я смотрел на проблему доказательной эквивалентности (перестановки правил) фрагмента линейной логики.

cc.complexity-theory lo.logic decision-trees boolean-formulas Марк
источник

Разве вы не можете использовать сокращенные диаграммы бинарных решений? Изменить: возможно, нет, ваши переменные не упорядочены ...

Сильвен

@Kaveh Нет, это происходит в теории доказательств: я смотрю на проблему эквивалентности доказательств (перестановку правил) фрагмента линейной логики. Сводится к этой логической проблеме. Поскольку я не специалист, я решил, что когда-нибудь задам вопрос, если бы это был хорошо известный / простой вопрос. Следовательно, да, я придумал имя, потому что я не знаю ничего лучше.

Марк

@ Марк, как правило, хорошая идея объяснить, почему ты интересуешься проблемой. Я редактировал вопрос. Пожалуйста, посмотрите, чтобы убедиться, что все в порядке. (Также удаляю мои предыдущие комментарии, так как они больше не нужны.)

Kaveh

@Kaveh Да, прости за это. Я отредактировал вашу переформулировку, чтобы приблизить ее к моему первоначальному аргументу (я не мог сразу понять, если ваш был в порядке, поэтому казалось, что это легче сделать)

Марк

Ответы:

Я нашел частичное решение. Проблема в Л.

Отрицанием эквивалентна , которая эквивалентна тогда и только тогда как и есть. $A \leftrightarrow B$ $(\bar A \land B) \lor (A \land \bar{B})$ $False$ $(\bar A \land B)$ $(A \land \bar{B})$

$\bar{A}$ $A$ $True$ $False$ $A$

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

Так что проблема как минимум в Л.

$AC_0$

РЕДАКТИРОВАТЬ 2: там это, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

Таким образом, проблема действительно завершена в Logspace.

Марк
источник

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$

Проще всего это сформулировать так: каждый путь является минимальным или максимальным в зависимости от метки своего листа. Мы проверяем, имеют ли они одинаковые минимальные условия. Мы можем перечислить min-термины в лог-пространстве и проверить, совпадают ли два min-термина в лог-пространстве.

Каве

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$

Денис
источник

x, y, z

$x,y,z$

x, \bar{y}, z

$x,\bar y,z$

x, y, \bar{z}

$x,y,\bar z$

Ах да, забыл это, я добавляю исправление, надеясь, что это работает сейчас.

Денис

Не забывайте требовать свой миллион долларов, если он работает :)

Marc

L

$L$