Удивительные алгоритмы подсчета проблем

54

Существуют некоторые проблемы подсчета, которые включают экспоненциальный подсчет многих вещей (относительно размера входных данных), и в то же время имеют удивительные точные, детерминированные алгоритмы за полиномиальное время. Примеры включают в себя:

Подсчет идеальных совпадений в плоском графе ( алгоритм FKT ), который является основой для работы голографических алгоритмов .
Подсчет остовных деревьев в графе (по теореме Кирхгофа о матричном дереве ).

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

Мой вопрос: существуют ли какие-либо «удивительно эффективные» точные и детерминированные алгоритмы, известные для подсчета проблем, которые не сводятся к вычислению определителя?

cc.complexity-theory counting-complexity big-picture Эшли Монтанаро
источник

8

Кстати, еще много проблем со счетом сводятся к вычислению детерминанта. Целочисленный определитель завершен для класса GapL, который содержит #L.

5501

11

Я не знаю, сводятся ли следующие проблемы к вычислению детерминанта или нет, но я все равно перечислю:

$v_0$ $v_f$ $v_f$ $v_0$

2) Подсчет числа решений задач, определяемых в MSO-логике в структурах ограниченной ширины дерева. Посмотрите, например, статью, посвященную работам Курселя, Арнборга и других .

$f:\{0,1\}^{n}\rightarrow \{0,1\}$ $x$ $f(x)=1$ $U_f$ $|x\rangle|0\rangle$ $|x\rangle|f(x)\rangle$ $|1\rangle$ $U_fH^{\otimes n}|0\rangle|0\rangle$

Матеус де Оливейра Оливейра
источник

Спасибо - пункты (2) и (3) интересны, но почему-то не совсем то, что я искал; проблемы подсчета с ограниченной шириной дерева больше походят на особые случаи, когда структура, с которой вы работаете, фактически ограничена полиномиально. Меня больше интересовали случаи, когда «реально» экспоненциально много объектов для подсчета, но их можно каким-то волшебным образом подсчитать за полиномиальное время.

Эшли Монтанаро

Не означает ли это, что если вы используете унарную кодировку, алгоритму нужно экспоненциальное время, чтобы просто записать число? Возможно ли, что эта проблема будет преодолена с помощью бинарного кодирования, но это звучит для меня непреложно.

Антонио Валерио Мицели-Бароне

2

@ Miceli-Barone, То, что вы говорите, будет относиться практически ко всем алгоритмам поли времени, которые выводят число. Сам детерминант был бы довольно большим в худшем случае в унарном.

Рафаэль

\frac{(n + 1)^{\frac{n + 1}{2}}}{2^{n}}

$\frac{(n + 1)^{\frac{n+1}{2}}}{2^n}$

11

Подсчет количества точек решетки в рациональном многограннике (когда размерность постоянна) за полиномиальное время , по мнению Александра Барвинок.

Ёсио Окамото
источник

2

какая основная техника?

Суреш Венкат

2

Короткая производящая функция. Следующая пояснительная статья даст нам больше идей. arxiv.org/abs/math/0506466

Ёсио Окамото

11

В рамках Холанта, есть несколько случаев, которые можно трактовать (по нетривиальным) причинам, кроме как через спичечные ворота в плоских графах.

1) Ворота Фибоначчи

2) Любой набор аффинных подписей .

3) неотрицательные взвешенные #CSP

...назвать несколько.

Кроме того, теорема BEST дает алгоритм полиномиального времени для подсчета числа эйлеровых цепей в ориентированном графе, хотя часть алгоритма действительно использует вычисление определителя.

Тайсон Уильямс
источник

Удивительные алгоритмы подсчета проблем

Ответы: