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

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

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

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

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