Existen toneladas de problemas NP-completos y fuentes que los recopilan, por ejemplo, vea el libro de Garey y Johnson. Me interesaría ver una lista de problemas NEXP-complete también. ¿Hay uno disponible? Como supongo que no hay, abro esta pregunta (¿se supone que es una wiki comunitaria? No sé...
¿Es posible que ? ¿Hay consecuencias interesantes de tal contención? ¿Contradeciría la hipótesis del tiempo exponencial?SAT¯¯¯¯¯¯¯¯¯¯∈NTIME(exp(n0.9))SAT¯∈NTIME(exp(n0.9))\overline{SAT} \in
Tengo un problema que está en NEXP NP y también se puede resolver con una TM alterna usando tiempo exponencial y solo una alternancia (comenzando en un estado existencial).notario públicoNP^{\text{NP}} ¿Se sabe algo sobre NEXP NP ? ¿Es igual a NEXP o alguna otra clase? ¿Hay problemas completos...
¿ implica E = N E ?E XP = N E X PEXP=NEXP\mathsf{EXP}=\mathsf{NEXP}E = N