Impagliazzo, Paturi y Calabro, Impagliazzo, Paturi introdujeron la hipótesis del tiempo exponencial (ETH) y la hipótesis del tiempo fuertemente exponencial (SETH). Aproximadamente, SETH dice que no existe un algoritmo que resuelva SAT en el tiempo .
Me preguntaba qué significaría romper con SETH. Definitivamente necesitamos encontrar un algoritmo que resuelva SAT en menos de pasos, pero no entiendo qué modelo computacional deberíamos usar. Hasta donde yo sé, los resultados basados en SETH (ver, por ejemplo, Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom ) no necesitan hacer suposiciones sobre el modelo subyacente de cómputo.
Supongamos, por ejemplo, que encontramos un algoritmo que resuelve SAT en el tiempo usando el espacio 1.5 n . ¿Implica automáticamente que podemos encontrar una máquina de Turing que resuelva este problema en el tiempo 1.99 n ? ¿Se rompe SETH?
fuente