Каноническое представление бинарного дерева решений в Ptime?

Мне интересно, может ли существовать способ придать своего рода «нормальную форму» бинарным деревьям решений (BDT) в управляемом виде.

Точнее: BDT - это дерево с внутренними узлами, помеченными логическими переменными, и листьями, помеченными $0$ или $1$ . BDT представляет логическую функцию очевидным образом. Два BDT $A,B$ эквивалентны ( $A\sim B$ ), когда они представляют одну и ту же функцию.

Существует ли функция $f$ которая вводит БРЭ и превращает ее в некоторую другую структуру данных, такую ​​что:

1. $f$ находится в Ptime
2. $f(A)=f(B)$ тогда и только тогда, когда$A\sim B$
3. $f$ имеет псевдообратную$g$ , то есть$g(f(A))\sim A$ , также в Ptime

Например, уменьшенные упорядоченные двоичные диаграммы принятия решений OBDD проверяют 2 и 3, но не 1, потому что при неправильном упорядочении переменных выходные данные могут иметь экспоненциальный размер.

У меня есть ощущение, что это может быть невозможно, но я не нашел никаких доказательств этого нигде.

Чтобы прокомментировать предложение Рики Демера:

В этой статье определяются классы (классы эквивалентности в Ptime) и K e r (полный инвариант в Ptime) и CF (каноническая форма в Ptime). Они изучают различные (маловероятные) значения P E q = K e r и K e r = C F, но не дают однозначного ответа на эти вопросы.$PEq$$Ker$$PEq=Ker$$Ker=CF$

Различные отрицательные ответы (невозможность 1 и 2, 1 и 2 и 3) на этот вопрос могли бы дать результаты разделения в виде или K e r ≠ C F ..., что до сих пор кажется открытой проблемой.$PEq\neq Ker$$Ker\neq CF$

Я думаю, что при условии, что , такого канонического представления не существует. Доказательство. Предположим, такое каноническое представление существует. Тогда функция A ↦ g ( f ( A ) ) может быть вычислена за полиномиальное время, поэтому, в частности, | g ( f ( A ) ) | является поли ( | A | ) . Но если мы возьмем B как минимальный BDT, эквивалентный A , то$\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$$A \mapsto g(f(A))$$|g(f(A))|$$\text{poly}(|A|)$$B$$A$ , поэтому | g ( f ( A ) ) | является поли ( | B | ) . Такой алгоритм приближения подразумевает, что N P ⊆ S U B E X P , согласноответу на другой пост, если я правильно понимаю.$g(f(A)) = g(f(B))$$|g(f(A))|$$\text{poly}(|B|)$$\mathsf{NP} \subseteq \mathsf{SUBEXP}$