¿Complejidad del tiempo con exponente irracional?

21

¿Hay algún problema natural en P para el cual el límite de tiempo de ejecución más conocido sea de la forma , donde es una constante irracional ?O(norteα)α

Andras Farago
fuente
44
Buena pregunta! :)
Michael Wehar
1
vea también la proporción áurea o en el tiempo de ejecuciónπ . esto podría ser una gran lista ...
vzn
La clasificación de un conjunto múltiple es alrededor de nH + n, por lo que si pudieras hacer que H (entropía) converja a algún que técnicamente calificaría. Sin embargo, no lo llamaría "natural". Sin embargo, puede haber un problema más natural en el que la entrada se reduce de esta manera. norteα-1
KWillets

Respuestas:

22

Si bien es cierto que no he hecho el análisis, y esto no es estrictamente un problema de decisión, estoy dispuesto a apostar que los algoritmos de multiplicación de matrices más conocidos (por Coppersmith, Winograd, Stothers, Williams, et al) tienen exponente irracional.

Esto se puede ver más claramente en el caso simple del algoritmo de Strassen, que tiene un tiempo de ejecución .O(norteIniciar sesión27 7)

Y, esto no es exactamente lo que preguntaste, pero Ryan Williams ha demostrado que todos los algoritmos que resuelven SAT en el espacio requieren tiempo n 2 cos ( π / 7 ) - o ( 1 ) , que es otro interesante e inusual aparición de una constante irracional en TCS.norteo(1)norte2cos(π/ /7 7)-o(1)

Joe Bebel
fuente
3
Los algoritmos más allá del algoritmo de Strassen realmente no se ejecutan en para su exponente establecido α . Más bien, por cada ϵ > 0 corren en O ϵ ( n α + ϵ ) . Esto se debe a varios límites involucrados en la obtención de α . O(norteα)αϵ>0 0Oϵ(norteα+ϵ)α
Yuval Filmus
12
La complejidad temporal del algoritmo de Strassen es realmente un artefacto de una recurrencia maestra resolviendo a Θ ( n log b a ) . Puede encontrar muchos de sus números irracionales favoritos creando instancias a y b con diferentes valores. T(norte)=unaT(norte/ /si)+F(norte)Θ(norteIniciar sesiónsiuna)unasi
Huck Bennett
Sí, estoy de acuerdo con ambos. Pensé que ya estaba siendo flojo con la definición de P, y no haber verificado si los exponentes de multiplicación de matrices son irracionales. Aunque me sorprendería si fueran racionales, dada la forma en que se derivan. En el fondo, las multiplicaciones rápidas de matrices aún se hacen eco del método básico de dividir y conquistar de Strassen, aunque ahora se describe en lenguaje tensorial. En realidad, aunque es fácil construir algoritmos como los describe con un irracional b a , no puedo pensar en ningún otro algoritmo natural de dividir y conquistar con esa propiedad, además de la multiplicación. Iniciar sesiónsiuna
Joe Bebel
Algunos algoritmos de multiplicación de enteros tienen exponentes irracionales si no recuerdo mal.
Yuval Filmus
Correcto, como el de Karatsuba. Pero sigue siendo multiplicación :)
Joe Bebel