Предельная вероятность генерации дерева

Question

Зафиксируйте некоторые конечные граф $ g= (v, e) $ и некоторые вершины $ x $

Предположим, я генерирую случайное поддеревку $ g $ размером $ n $ , содержащий $ x $ , следующим образом:

1. Пусть $ t_0={x \} $ .

2. для $ 0

   я. Пусть $ b_n $ Будьте набор соседей $ t_ {n - 1} $ вне $ t_ {n-1} $ .

   II. Форма $ t_n $ путем

   .
   • образец пара $ (x_n, y_n) \ in e (g) \ cap \ left (v (t_ {n - 1}) \ turs b_n \ vant) $ < / span>, с вероятностью $ q_n (x_n, y_n | t_ {n - 1}) $ ,
   • Добавить $ y_n $ на $ v (t_ {n - 1}) $ и добавить $ (x_n, y_n) $ на $ e (t_ {n - 1}) $ .

3. return $ t_n $ .

Предположим также, что $ q_n (x_n, y_n | t_ {n - 1}) $ можно легко вычислить для всех $ (T_ {n-1}, x_n, y_n) $ . Я заинтересован в эффективном и точно вычислении предельной вероятности генерации дерева $ t_n $ , учитывая, что я начал расти в $ T_0={x \} $ , т.е.

$$ p (T_n | T_0={x \})=sum_ {x_ {1: n}, y_ {1: n}} \ prod_ {n= 1} ^ n q_n (x_n, y_n | t_ {n - 1}). $$

Мой вопрос по сути, следует ли ожидать ли я иметь возможность найти эффективный алгоритм (I.e. Polynomial-Time) алгоритм для этого, и если это так, то, что это может быть.

Некоторые мысли:

.

• наивно, сумма имеет экспоненциально-много терминов, которые препятствуют, пытаясь оценить сумму напрямую.

• С другой стороны, эта проблема также высоко структурирована (деревья, рекурсион и т. Д.), Возможность предположить, что какой-то динамический подход программирования будет возможен. Я не уверен, как точно подходить.

• , я знаю, как рассчитать беспристрастные, неотрицательные оценки $ p (t_n | t_0={x \}) $ , который имеют разумную дисперсию свойств, используя методы от последовательной фильтрации Monte Carlo / частиц. Это говорит о том, что проблема, по крайней мере, возможна, чтобы хорошо приблизиться в разумном количестве времени.

Answer 1

нет. Если $ q (x_n, y_n | t_ {n - 1}) $ - это произвольно - может быть произвольная зависимость от $ T_ {n-1} $ - тогда это требует экспоненциального времени.

Рассмотрим дерево $ t_n $ , который имеет один корневой узел, $ N-1 $ листья и край от корня на каждый лист. Существуют $ 2 ^ n $ Поддеревы $ t_n $ , а в частности, есть <класс SPAR= «Математический контейнер»> $ 2 ^ n $ Возможные значения $ t_n $ , которые могут возникнуть в выражении

$$ \ sum_ {x, y} \ prod_ {n= 1} ^ n q_n (x_n, y_n | t_ {n - 1}). $$

можно использовать простым противником, чтобы доказать, что оценка этого выражения требует экспоненциального времени. Предположим, что мы оцениваем $ q_n (x_n, x_n | t_ {n - 1}) $ , запросивая Oracle с помощью $ X_N , y_n, t_ {n - 1} $ . Предположим, что есть одно дерево $ t $ , который никогда не впрочен в oracle как любой $ t_ {n - 1} $ . Выберите все значения $ q_n (\ cdots) $ значений строго положительного. Тогда, поскольку $ q_n (x_n, y_n | t) $ не было запрошено во время выполнения, мы можем выбрать его после наблюдения за выходом алгоритма; Но, изменяя его, мы можем выбрать значение, которое делает вывод алгоритма неверным (в частности, значение выражения зависит от $ q_n (x_n, y_n | t) $ Но вывод алгоритма не зависит от $ q_n (x_n, y_n | t) $ , поэтому выход алгоритма не может исправить). Мы доказали, что для создания правильного выхода любой правильный алгоритм должен запрашивать Oracle для всех 2 $ ^ n $ Возможные подделки $ T_n $ . Для запроса Oracle требуется как минимум $ O (1) $ Запросить Oracle.

В заключение этот аргумент доказывает, что любой правильный алгоритм вычисления этого выражения должен принимать $ \ Omega (2 ^ n) $ время.

Я не знаю, всегда может быть, всегда можно сделать в $ O (2 ^ n) $ Время или возможно ли