← Glosario Término
Exponential Time Hypothesis
Una suposición ampliamente confiable en informática de que algunos acertijos de lógica difícil no pueden resolverse rápidamente en el peor de los casos.
El Exponential Time Hypothesis dice que para un famoso tipo de rompecabezas, llamado SAT (encontrar valores que hagan verdadera una afirmación lógica), no existe un atajo inteligente. En el peor de los casos, el tiempo necesario se duplica aproximadamente con cada variable adicional, lo que se vuelve imposible muy rápidamente.
Nadie lo ha demostrado, pero cientos de artículos de investigación asumen que es cierto y se basan en ello. Si alguien realmente lo refutara, esos artículos perderían fundamento, aunque sus resultados aún pudieran ser correctos.
Mencionado en