¿Existen algoritmos de tiempo subexponencial para problemas de NP completo?

51

¿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 .nlogn

ksb
fuente
10
¿Qué quieres decir con "sub-exponencial"? Si quiere decir , la respuesta es definitivamente sí. Si te refieres a 2 n o ( 1 ) , creo que la respuesta es no. 2o(n)2no(1)
JeffE

Respuestas:

57

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)

2no(1)NP2no(1)

NP

0<ϵ2O(nϵ)2O(nϵ) 0<ϵ

La situación es similar a la anterior.

NP


ϵ<12O(nϵ)2O(nϵ) ϵ<1

2O(nϵ)ϵ<1

NP2O(n)nk

SAT={φ,wφSAT and |w|=|φ|k}

NP2O(n1k)

2o(n)

Contiene la clase anterior, la respuesta es similar.

0<ϵ2ϵn2ϵn ϵ>0

Contiene la clase anterior, la respuesta es similar.

ϵ<12ϵn2ϵn ϵ<1

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 .

nlgn

2Θ(n)2nΘ(1)

ΘoϵΘϵϵ>0Θϵϵ<1

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.

Exp2nO(1)

SubExp

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.

LPNPPSpaceExp

Veraniego

NP

Kaveh
fuente
77
Esta respuesta debería ir a Wikipedia.
Erel Segal-Halevi
32

2O(nlogn)nO(1)2O(n)nO(1)

Pål GD
fuente
1
2O(nϵ)ϵ<12no(1)