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

10

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

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

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

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

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

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


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

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

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

Марк
источник
1
Является даже известно, что в Ptime?
1
Независимо от того, что ваш вопрос эквивалентен «Имеют ли иметь в канонической форме FP ?».
Спасибо, Рикки Демер, я не знал, что системный подход к этому вопросу существовал.
Марк
Почему «отрицательный ответ на этот вопрос» «дает результат разделения »?PEqKer

Ответы:

9

Я думаю, что при условии, что , такого канонического представления не существует. Доказательство. Предположим, такое каноническое представление существует. Тогда функция A g ( f ( A ) ) может быть вычислена за полиномиальное время, поэтому, в частности, | g ( f ( A ) ) | является поли ( | A | ) . Но если мы возьмем B как минимальный BDT, эквивалентный A , тоNPSUBEXPAg(f(A))|g(f(A))|poly(|A|)BA , поэтому | g ( f ( A ) ) | является поли ( | B | ) . Такой алгоритм приближения подразумевает, что N PS U B E X P , согласноответу на другой пост, если я правильно понимаю.g(f(A))=g(f(B))|g(f(A))|poly(|B|)NPSUBEXP

Уильям Хоза
источник
Мне было известно только об «ответе 2» из этого поста. Поэтому я начал те же рассуждения, но застрял на этом пути.
Марк
Было бы хорошо, чтобы обернуть это в автономном режиме, хотя. Я постараюсь прочитать статью, на которой основывается претензия к посту: researchcher.watson.ibm.com/researcher/files/us-vitaly/… и сделаю это.
Марк
1
Я боюсь, что есть проблема с «ответом 3» из этого ответа. Я спросил об этом автора, но не получил обратной связи.
Марк