¿Hay problemas de NP completo que hayan probado algoritmos de tiempo subexponencial?
Estoy solicitando las entradas de casos generales, no estoy hablando de casos especiales manejables aquí.
Por sub-exponencial, me refiero a un orden de crecimiento por encima de los polinomios, pero menos que exponencial, por ejemplo .
Respuestas:
Depende de lo que quieras decir con subexponencial. A continuación, explico algunos significados de "subexponencial" y lo que sucede en cada caso. Cada una de estas clases está contenida en las clases debajo de ella.
I.2no(1)
La situación es similar a la anterior.
Contiene la clase anterior, la respuesta es similar.
Contiene la clase anterior, la respuesta es similar.
Contiene la clase anterior, la respuesta es similar.
¿Qué significa subexponencial?
"Por encima del polinomio" no es un límite superior, sino un límite inferior y se conoce como superpolinomial .
Cuál debería llamarse subexponencial es discutible. Por lo general, las personas usan el que necesitan en su trabajo y se refieren a él como subexponencial.
III se usa para límites superiores algorítmicos, como los mencionados en la respuesta de Pal.
IV también es común.
V se usa para establecer la conjetura ETH.
Veraniego
fuente
fuente