?

12

É possível que ? Existem conseqüências interessantes de tal contenção? Contrariaria a hipótese do tempo exponencial?SAT¯NTIME(exp(n0.9))

Igor Shinkar
fonte

Respostas:

17

É possível ;-)

Isso daria limites mais baixos ao novo circuito. Como você está assumindo um forte pressuposto, isso pode resultar do trabalho seminal de Impagliazzo, Kabanets e Wigderson , não verifiquei.

n1+Ω(1)nNPsO(s)O(s) variáveis ​​por Cook-Levin.

Isso não contradiz diretamente o ETH porque isso é para algoritmos determinísticos.

Manu
fonte
10

NTIME[2(1ε)n]

Huck Bennett
fonte