¿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 ?
cc.complexity-theory
time-complexity
polynomial-time
Andras Farago
fuente
fuente
Respuestas:
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 ( nIniciar 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 ) norte2 cos( π/ 7)-o(1)
fuente