Алгоритмы полиномиального времени с огромным показателем / постоянной

Знаете ли вы разумные алгоритмы, которые выполняются за полиномиальное время в (Длина ввода + Длина выхода), но у которых асимптотическое время выполнения в той же мере имеет действительно огромную экспоненту / постоянную (по крайней мере, когда доказанная верхняя граница времени выполнения находится в такой способ)?

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

Лемма регулярности Семереди говорит вам, что в любом графе по вершинам вы можете разбить вершины на множества, где ребра между парами множеств являются «псевдослучайными» (т. Е. Плотности достаточно больших подмножеств выглядят как плотности в случайном графе) , Это структура, с которой очень приятно работать, и, как следствие, существуют алгоритмы, использующие раздел. Подвох в том, что количество наборов в разделе является экспоненциальной башней по параметру псевдослучайности (см. Здесь: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma ).$n$

Некоторые ссылки на алгоритмы, основанные на лемме о регулярности, см., Например: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf.

Новости SODA 2013 : проблема Макс-Бисекции приблизительно равна 0,8776 за время .$O(n^{10^{100}})$

Вот два скриншота из «Энерго-ориентированного подхода к разворачиванию связей», подготовленного Джейсоном Х. Кантареллой, Эриком Д. Демейном, Хейли Н. Ибеном, Джеймсом Ф. О'Брайеном, SOCG 2004:

Вот недавний результат от FUN 2012 бумажных картинка висячих Пазлов Эрика Д. Demaine, Мартин Л. Demaine, Яир Н. Минский, Джозеф Б. Митчелл, Рональд Л. Ривестом и Михай PATRASCU.

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

Не позволяйте "полиномиальному числу" обмануть вас ... оказывается, .$O(n^{43737})$

Существует класс задач, решения которых трудно вычислить, но аппроксимировать их с любой точностью легко в том смысле, что существуют алгоритмы с полиномиальным временем, которые могут аппроксимировать решение с точностью до для любой постоянной ε> 0. Однако есть одна загвоздка: время работы аппроксиматоров может сильно зависеть от 1 / ,, например, быть O ( $(1+\epsilon)$$1/\epsilon$.$O(n^{1/\epsilon})$

Более подробная информация здесь: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .

Хотя во время выполнения таких алгоритмов были впоследствии улучшено, оригинальный алгоритм дискретизации точки из выпуклого тела было время выполнения .$\tilde{O}(n^{19})$

Дайер, Фриз и Каннан: http://portal.acm.org/citation.cfm?id=102783

Если является табличной модальной или суперинтуиционистской логикой, то расширенные системы доказательства Фреге и Фреге замещения для L полиномиально эквивалентны и полиномиально точно интерпретируются в классическом EF (это теорема 5.10 в моей статье ). Показатель c полиномиального моделирования явно не указан в теореме 5.10, но индуктивное доказательство теоремы дает c = 2 O ( | F | ) , где F - конечная система Крипке, порождающая L , поэтому она может быть такой же огромной как хотите в зависимости от логики. (Это ухудшается в теореме 5.20.)$L$$L$$c$$c=2^{O(|F|)}$$F$$L$

Текущий самый известный алгоритм для распознавания графов карт (обобщение плоских графов) работает в . Thorup, Карта графиков за полиномиальное время.$n^{120}$

Вычисление равновесия рынка Эрроу-Дебре требует расчетов максимального потока, где U - максимальная полезность. Дуан, Мелхорн, Комбинаторный полиномиальный алгоритм для линейного рынка Стрелка-Дебре.$O(n^6\log(nU))$$U$

Проблема быстротечности в песочнице

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

Рассмотрим следующую модель для вышеуказанного процесса. Смоделируйте плитку как сетку . Частицы песка сбрасываются по вершинам этой сетки. Если число частиц в вершине превышает ее степень, то эта вершина разрушается, и частицы в ней перемещаются в смежные вершины (каскадным образом). Частица песка, которая достигает граничной вершины, исчезает в раковине («отваливается»). Это называется абелевой моделью песочных свай$n \times n$ .

Проблема: сколько времени требуется, чтобы конфигурация стала периодической с точки зрения $n$ , предполагая худший алгоритм сбрасывания частиц песка?

В SODA '07 Ласло Бабай и Игорь Городецкий доказали, что на этот раз они ограничены полиномами, но ..

В SODA '12 Аюш Чуре и Сундар Вишванатан улучшили эту оценку до $O(n^7)$ .

Этот ответ выглядел бы немного лучше, если бы не их улучшение :)

Задача «выпуклый череп» состоит в том, чтобы найти выпуклый многоугольник максимальной площади внутри данного простого многоугольника. Самый быстрый алгоритм, известный для этой проблемы, выполняется за раз [Chang and Yap, DCG 1986].$O(n^7)$

Решение Annihilation Games (Френкель и Йеша) имеет сложность .$O(n^6)$

Существуют некоторые неконструктивные алгоритмы, особенно теорема Феллоуза, Лэнгстона и Курселя. .

Кроме того, алгоритм линейного времени Бодлендера для ширины дерева и теорема Курселя общеизвестно непрактичны.

$G$$O(n^3)$$H$$n$$G$$G$

http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition

$O(n^{11})$

В Polygon rectangulation, часть 2: Минимальное количество жирных прямоугольников , представлена ​​практическая модификация проблемы разделения прямоугольника, мотивированная проблемами в VLSI:

$P$$\delta$$P$$\delta$

$O(n^{42})$

$O(2^n)$$n$$n \choose 1$$n \choose 2$$n \choose 3$$O(n^c)$$c$$n \choose c$$c$$\mathsf{P \neq NP}$ или что - то покрепче.

[1] Вопросы о жесткости вычислительной матрицы

$c$$O(n^c)$$n \choose c$$\mathsf{P \neq NP}$