Complexidade temporal com expoente irracional?

Existe algum problema natural em P para o qual o limite de tempo de execução mais conhecido seja da forma , em que é uma constante irracional ? $O(n^\alpha)$ $\alpha$

cc.complexity-theory time-complexity polynomial-time Andras Farago
fonte

Boa pergunta! :)

Michael Wehar

veja também proporção áurea ou no tempo de execução

π

$\pi$ . isso poderia concebivelmente ser um big-lista ...

vzn

A classificação de um multiset é em torno de nH + n; portanto, se você conseguir que H (entropia) converja para alguns que tecnicamente se qualificarão. Eu não chamaria isso de "natural". No entanto, pode haver algum problema mais natural em que a entrada é reduzida dessa maneira.

n^{α - 1}

$n^{\alpha-1}$

KWillets

Embora eu não tenha feito a análise e isso não seja estritamente um problema de decisão, estou disposto a apostar que os algoritmos de multiplicação de matriz mais conhecidos (de Coppersmith, Winograd, Stothers, Williams, et al) têm expoente irracional.

Isso pode ser visto com mais clareza no caso simples do algoritmo de Strassen, que possui o tempo de execução . $O(n^{\log_2 7})$

E isso não é exatamente o que você pediu, mas Ryan Williams mostrou que todos os algoritmos que resolvem SAT no espaço requerem tempo , que é outra aparência interessante e incomum de uma constante irracional no TCS. $n^{o(1)}$ $n^{2 \cos(\pi/7) - o(1)}$

Joe Bebel
fonte

Algoritmos além do algoritmo de Strassen não são realmente executados em para o expoente declarado . Em vez disso, para cada eles são executados em . Isso ocorre devido a vários limites envolvidos na obtenção de .

O (n^{α})

$O(n^\alpha)$

α

$\alpha$

ϵ > 0

$\epsilon > 0$

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

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

α

$\alpha$

Yuval Filmus

A complexidade de tempo do algoritmo de Strassen é realmente um artefato de uma recorrência Mestre resolvendo para . Você pode vir até com muitos dos seus números irracionais favoritos por instanciar e com valores diferentes.

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$

Huck Bennett

Sim, eu concordo com os dois. Eu imaginei que já estava solto com a definição de P e não havia verificado se os expoentes de multiplicação da matriz são irracionais. Embora eu ficaria surpreso se eles fossem racionais, considerando como são derivados. No fundo, as multiplicações rápidas de matriz ainda ecoam o método básico de divisão e conquista de Strassen, embora agora seja descrito na linguagem tensorial. Na verdade, embora seja fácil construir algoritmos como você descreve com irrational , não consigo pensar em nenhum outro algoritmo natural de divisão e conquista com essa propriedade, além da multiplicação.

\log_{b} a

$\log_b a$

21715 Joe

Alguns algoritmos de multiplicação de números inteiros têm expoentes irracionais, se bem me lembro.

Yuval Filmus

Certo, como o de Karatsuba. Mas ainda é a multiplicação :)

Joe Bebel

Complexidade temporal com expoente irracional?

Respostas: