Złożoność czasu z irracjonalnym wykładnikiem?

Czy istnieje jakiś problem naturalny w P, dla którego najlepiej znanym ograniczeniem czasu przebiegu jest forma , gdzie jest stałą nieracjonalną ? $O(n^\alpha)$ $\alpha$

cc.complexity-theory time-complexity polynomial-time Andras Farago
źródło

Dobre pytanie! :)

Michael Wehar,

patrz także złoty współczynnik lub

w czasie działania

π

$\pi$ . może to być duża lista ...

wer

Sortowanie multisetu odbywa się w okolicach nH + n, więc jeśli można sprawić, że H (entropia) zbiegnie się do jakiegoś

, co technicznie by się kwalifikowało. Nie nazwałbym tego jednak „naturalnym”. Jednak może istnieć bardziej naturalny problem, w którym wkład jest zmniejszany w ten sposób.

n^{α - 1}

$n^{\alpha-1}$

KWillets

Odpowiedzi:

Chociaż co prawda nie przeprowadziłem analizy i nie jest to wyłącznie problem decyzyjny, jestem gotów postawić na najbardziej znane algorytmy mnożenia macierzy (Coppersmith, Winograd, Stothers, Williams i inni) mają irracjonalny wykładnik.

Widać to wyraźniej w prostym przypadku algorytmu Strassena, który ma czas działania . $O(n^{\log_2 7})$

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

Joe Bebel
źródło

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$

Niektóre algorytmy mnożenia liczb całkowitych mają nieracjonalne wykładniki, jeśli dobrze pamiętam.

Yuval Filmus,

Racja, jak u Karatsuby. Ale to wciąż mnożenie :)

Joe Bebel