Modelo Computacional em SETH

Impagliazzo, Paturi e Calabro, Impagliazzo, Paturi introduziram a Hipótese de tempo exponencial (ETH) e a Hipótese de tempo fortemente exponencial (SETH). Grosso modo, o SETH diz que não há algoritmo que resolva o SAT no tempo . $1.99^n$

Eu queria saber o que isso significaria para quebrar SETH. Definitivamente, precisamos encontrar um algoritmo que resolva o SAT em menos de etapas, mas não entendo bem qual modelo computacional devemos usar. Até onde eu sei, os resultados baseados no SETH (veja, por exemplo, Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom ) não precisam fazer suposições sobre o modelo subjacente de computação.$2^n$

Suponha, por exemplo, que encontramos um algoritmo que resolve SAT no tempo usando o espaço 1,5 n . Isso implica automaticamente que podemos encontrar uma máquina de Turing que resolva esse problema no tempo 1,99 n ? Isso quebra SETH?$1.5^n$$1.5^n$$1.99^n$

$\delta < 1$$k$$k$$2^{\delta n}$$O(\log N)$$N$

$2^{\delta n}$$2^{\delta n} \cdot poly(n)$ser eficientemente simulado com máquinas de Turing multitape). Observe que muitas primitivas computacionais (como classificação, avaliação de circuitos, programação dinâmica simples) podem ser implementadas eficientemente em máquinas Turing multitape. Uma referência relevante para essas questões é Regan, "Sobre a diferença entre o tempo da máquina de Turing e o tempo da máquina de acesso aleatório".

Para resolver suas perguntas específicas: não, uma máquina de Turing multitape não é automaticamente implícita aqui, mas sim, esse "algoritmo" para SAT (no modelo de acesso aleatório usual) quebraria SETH.