Решение задач в

Каковы некоторые примеры сложных проблем решения, которые могут быть решены за полиномиальное время? Я ищу проблемы, для которых оптимальный алгоритм является «медленным», или проблемы, для которых самый быстрый известный алгоритм является «медленным».

Вот два примера:

• Распознавание совершенных графов. В своей работе FOCS'03 [1] Корнежоль, Лю и Вускович дали временной алгоритм для задачи, где n - количество вершин. Я не уверен, была ли улучшена эта граница, но, насколько я понимаю, более или менее необходим прорыв, чтобы получить более быстрый алгоритм. (Авторы приводят алгоритм времени O ( n 9 ) в журнальной версии [1], см. Здесь ).$O(n^{10})$$n$$O(n^9)$

• Распознавание графов карт. Торуп [2] дал довольно сложный алгоритм с показателем (около?) . Возможно, это даже значительно улучшилось, но у меня нет хороших рекомендаций.$120$

Меня особенно интересуют проблемы, которые имеют практическое значение, и получение «быстрого» (или даже практического) алгоритма было открыто в течение нескольких лет.

[1] Корнежоль, Жерар, Синьмин Лю и Кристина Вускович. «Полиномиальный алгоритм распознавания совершенных графов». Основы информатики, 2003. Труды. 44-й ежегодный симпозиум IEEE. IEEE, 2003.

[2] Торуп, Миккель. «Карта графиков за полиномиальное время». Основы информатики, 1998. Труды. 39-й ежегодный симпозиум IEEE, 1998.

Возможно, следующие проблемы вписываются в ваши примеры:

• (Версия решения) Раскраска, Клика, Стабильный Набор, Клик Покрытие в идеальных графиках. До сих пор единственные известные алгоритмы полиномиального времени для этих задач основаны на методе эллипсоидов, который является «медленным» (и численно нестабильным).

• AKS-тест на простоту за раз. Несмотря на множество улучшений (в настоящее время O ( ( log n ) 7.5 ) ), алгоритм AKS все еще слишком медленный на практике.$O((\log n)^{12})$$O((\log n)^{7.5})$

Есть аналогичный вопрос по теории , со множеством примеров, начиная от «реально невыполнимо медленных» алгоритмов с показателями от 6 до 7 и выше. Этот вопрос также обсуждает большие константы.

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

$1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$

$117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

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