Какая проблема NP-Complete имеет самый быстрый известный алгоритм?

С точки зрения асимптотического времени выполнения в наихудшем случае, какая NP-полная задача имеет самый известный (точный) алгоритм и что это за алгоритм? Известно ли что-то, что быстрее, чем ? $O(n^2*2^n)$

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
источник

Какой алгоритм имеет время работы

? РЕДАКТИРОВАТЬ: я предполагаю, что вы имеете в виду алгоритм Хелд-Карп для коммивояжера.

O (n^{2} \cdot 2^{n})

$O(n^2 \cdot 2^n)$

Гильденстерн

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

Пол GD

«Быстрее, чем

» не имеет смысла. Вы имеете в виду

? Или вопрос: есть ли алгоритм с лучшей проверенной верхней границей времени выполнения, чем

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Рафаэль

Последний. Это верный момент; мог бы быть алгоритм A, который быстрее чем B на практике, но не с более жесткой верхней границей. Я не уверен, почему не имеет смысла говорить «быстрее, чем верхняя граница», а не «быстрее, чем нижняя и верхняя граница» ...

Wuschelbeutel Kartoffelhuhn

Ответы:

$1.2738^k + nk$ $2^n n^2$ $k=n$ $n$ $k$

Кроме того, вопрос Существуют ли субэкспоненциальные алгоритмы времени для NP-полных задач? обращается к аналогичным вопросам.

Пол Г.Д.
источник

В вопросах задаются вопросы о самых быстрых из известных алгоритмов, и в таблице, на которую вы ссылаетесь , есть «более быстрые» алгоритмы, чем у VC (в частности, субэкспоненциальные), так что, вероятно, это не лучший пример для цитирования.

Рафаэль

См. Также этот похожий вопрос и ответ Дэвида Эппштейна. Наилучшее время выполнения для решения задачи NP-Complete о mathoverflow.

Пол GD

ϵ > 0

$\epsilon > 0$

O ((1 + ϵ)^{k} + poly (n))

$O( (1+\epsilon)^k + \text{poly}(n))$