Распределение вероятностей и вычислительная сложность

Этот вопрос о пересечении теории вероятностей и сложности вычислений. Одним из ключевых замечаний является то, что некоторые распределения проще генерировать, чем другие. Например, проблема

Для заданного числа вернуть равномерно распределенное число с . $n$ $i$ $0 \leq i < n$

легко решить. С другой стороны, следующая проблема является или кажется намного более сложной.

Получив число , верните число такое, что является (числом Гёделя) действительным доказательством длины n в арифметике Пеано. Более того, если количество таких доказательств равно , то вероятность получить какое-либо конкретное доказательство длины должно быть . $n$ $i$ $i$ $pr(n)$ $n$ $\frac{1}{pr(n)}$

Это наводит меня на мысль, что вероятностные распределения приходят с понятием вычислительной сложности. Более того, эта сложность, вероятно, тесно связана с лежащими в основе проблемами решения (будь то субрекурсивная, например, , , рекурсивная, рекурсивно перечислимая или хуже). $P$ $EXP$

Мой вопрос: как определить вычислительную сложность вероятностных распределений, особенно когда основная проблема решения не разрешима. Я уверен, что это уже расследовано, но я не уверен, где искать.

complexity-theory reference-request probability-theory probabilistic-algorithms Мартин Бергер
источник

Другой интересный пример (но разрешимый) - квантовое преобразование Фурье. Если вернуть число такое, что вероятность пропорциональна, .

f (k) = a^{k} \mod b

$f(k)=a^k \mod b$

l \in [0, N]

$l \in [0,N]$

l

$l$

| F (l) |

$\left|F(l)\right|$

F (l) = \sum_{k = 0}^{N} f (k) e^{- 2 π i k l / N}

$F(l) = \sum_{k=0}^N f(k) e^{-2\pi ikl/N}$

Блуждающая логика

Оба ваших примера представляют собой дискретные равномерные распределения. Я полагаю, что разные сложности заключаются в том, насколько сложно сосчитатьгде это поддержка.

| χ |

$|\chi|$

χ

$\chi$

Николас Манкузо

@NicholasMancuso Я согласен, что всегда можно использовать подсчет + неформальный выбор. Так что в некотором смысле это дает верхнюю границу. Это все, что можно сказать? Где в литературе это было исследовано?

Мартин Бергер

@NicholasMancuso Примеры, которые я привожу, представляют собой равномерное распределение. Но можно задать тот же вопрос о неравномерных распределениях. Можно также задаться вопросом о распределениях на . Что касается дискретных распределений: prima facie, подсчета в общем недостаточно, необходимо также иметь возможность генерировать элемент после того, как вы равномерно выбрали . Тем не менее, это может быть случай, когда подсчет является ядром проблемы.

R

$\mathbb{R}$

i

$i$

i

$i$

Мартин Бергер

@NikosM. Спасибо, но эта ссылка тоже ничего не говорит о сложности базового дистрибутива. Ссылка говорит о преобразовании на равномерном распределении. Но это преобразование может быть сложным или легким в вычислительном отношении.

ϕ

$\phi$

Мартин Бергер

Сложность вероятностных распределений проявляется, в частности, при изучении таких распределительных задач, как DistNP, в теории Левина о средней сложности дел .

Распределение является P-вычисляемым, если его кумулятивная функция плотности может быть оценена за полиномиальное время.

Распределение является P-выборочным, если мы можем выбрать из них за полиномиальное время.

Если распределение является P-вычислимым, то оно является P-выборочным. Обратное неверно, если существуют определенные односторонние функции.

Вы можете расширить определения для других классов сложности.

У Одеда Голдрайха есть хорошие вводные заметки по теме, которые вы, возможно, захотите проверить.

Кава
источник

Спасибо, я думаю, что теория выборочных распределений является чем-то вроде того, что я искал. Но нет никаких оснований ограничивать внимание на , вы можете определить -samplable распределения для любого класса сложности . С недавним ростом вероятностных языков программирования это становится жизненно важным.

P

$P$

P

$P$

C

$C$

C

$C$

Мартин Бергер

@ Мартин, да. На NIPS 2015 было учебное пособие по вероятностному программированию ( слайды , видео также будет опубликовано). Я слышал, что люди, которые посетили его, находили его очень интересным. Приятно видеть людей, работающих на пересечении ML / Stats и PL. :)

Каве

Да, и главная проблема в том, что такие языки (= универсальные, программируемые сэмплеры) работают медленно. Как мы можем ускорить их?

Мартин Бергер

Распределение вероятностей и вычислительная сложность

Ответы: