Временная сложность с иррациональным показателем?

Существует ли естественная проблема в P, для которой наилучшая известная временная граница имеет вид , где - иррациональная постоянная? $O(n^\alpha)$ $\alpha$

cc.complexity-theory time-complexity polynomial-time Андрас Фараго
источник

Аккуратный вопрос! :)

Майкл Вехар

см. также золотое сечение или

во время работы

π

$\pi$ . это может быть большой список ...

vzn

Сортировка мультимножества составляет около nH + n, поэтому, если бы вы могли получить H (энтропию), чтобы сходиться к некоторому

, что технически соответствовало бы. Я бы не назвал это "естественным", хотя. Однако может возникнуть более естественная проблема, когда таким образом уменьшается вклад.

n^{α - 1}

$n^{\alpha-1}$

KWillets

Ответы:

Хотя, по общему признанию, я не проводил анализ, и это не является строго проблемой решения, я готов поставить самые лучшие алгоритмы умножения матриц (по Coppersmith, Winograd, Stothers, Williams и др.) С иррациональным показателем.

Это можно увидеть более четко в простом случае алгоритма Штрассена, который имеет время работы . $O(n^{\log_2 7})$

$n^{o(1)}$ $n^{2 \cos(\pi/7) - o(1)}$

Джо Бебель
источник

O (n^{α})

$O(n^\alpha)$

α

$\alpha$

ϵ > 0

$\epsilon > 0$

O_{ϵ} (n^{α + ϵ})

$O_\epsilon(n^{\alpha+\epsilon})$

α

$\alpha$

T (n) = a T (n / b) + f (n)

$T(n) = a T(n/b) + f(n)$

Θ (n^{\log_{b} a})

$\Theta(n^{\log_b a})$

a

$a$

b

$b$

\log_{b} a

$\log_b a$

Некоторые алгоритмы умножения целых чисел имеют иррациональные показатели, если я правильно помню.

Юваль Фильмус

Точно, как у Карацубы. Но это все еще умножение :)

Джо Бебель