Modelo computacional en SETH

11

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 . 1.99n

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.2n

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?1.5n1.5n1.99n

Alex Golovnev
fuente

Respuestas:

18

δ<1kk2δnO(logN)N

2δn2δnpoly(n)simularse eficientemente con máquinas de Turing multitapa). Tenga en cuenta que muchas primitivas computacionales (como clasificación, evaluación de circuitos, programación dinámica simple) se pueden implementar de manera eficiente en máquinas Turing de múltiples cintas. Una referencia relevante para estos problemas es Regan, "Sobre la diferencia entre el tiempo de máquina de Turing y el tiempo de máquina de acceso aleatorio".

Para abordar sus preguntas específicas: no, una máquina de Turing multitapa no está automáticamente implicada aquí, pero sí, un "algoritmo" para SAT (bajo el modelo habitual de acceso aleatorio) rompería SETH.

Ryan Williams
fuente
3
δ=1
2
No exactamente. Arreglé los cuantificadores.
Ryan Williams
¿Qué pasa con las computadoras cuánticas en este contexto? ¿No hay consecuencias del algoritmo de Grover en este contexto? ¿Hay algún trabajo en asumir un análogo cuántico de la ETH?
Martin Schwarz
2n/2
Claro, pero ¿estas aceleraciones mejores que las clásicas y el "quatum SETH" ya tienen alguna implicación en algún otro lugar de la teoría de la complejidad? Sólo me preguntaba.
Martin Schwarz