Пример непрактичного алгоритма, известного как P?

Question

Общепринято, что проблемы, которые могут быть решены за полиномиальное время, «поддаются решению», а алгоритмы, требующие больше времени, чем неразрешимые. Конечно, решение за полиномиальное время ничего не говорит об абсолютной эффективности; например, то, что выполняется во времени n ¹⁰⁰⁰ , на практике совершенно нецелесообразно.

Хотя я видел довольно много алгоритмов полиномиального времени, я никогда не видел ни одного для практической задачи, которая бы работала больше, чем O (n ⁴ ), которая была оригинальной версией Алгоритм соответствия Эдмондса.

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

РЕДАКТИРОВАТЬ: Чтобы уточнить, я, вероятно, должен сказать, что я ищу алгоритм с огромным показателем степени проблемы, а не сложный для реализации алгоритм или алгоритм с огромной константой фактор. Как отметил Морон, существует много известных непрактичных алгоритмов с большой асимптотикой.

Answer 1

PRIMES в P: Проверка простоты AKS , сложность O (n ⁶ ), где n = log N - количество битов, используемых для кодирования основного кандидата. *

Хотя это прекрасный теоретический результат, тестирование на простоту обычно выполняется с помощью теста Миллера-Рабина или других рандомизированных алгоритмов.

Answer 2

Да, проблема линейного программирования . Хорошо известный алгоритм simplex является неполиномиальным, хотя существует алгоритм полинома (я думаю, что n ^ 5), который в практике работает намного медленнее, чем экспоненциальный из-за очень большого коэффициента

Answer 3

Слишком много проблем: Проблема упаковки в бункер с ограниченным кругом , для k (постоянное значение k) имеет алгоритм O (n ^ 2k), поэтому для k = 3 нецелесообразно (если оно больше, чемn ^ 4 непрактично).

Multiway k-Cut с заданным k (is P), sqrt (2) (честно говоря, не в NP), ...

Но я думаю, что это не такважно, что они практичны или непрактичны, во многих случаях они являются ограниченной версией задач NP-Hard, и мы можем изменить эту ограниченную версию на какой-то другой экземпляр с принятием некоторой ошибки, чтобы иметь лучший алгоритм (например, то, что мы делаем в простых числах,или то, что мы делаем с упаковкой бина-> ограниченная упаковка бина).