Seja SAT o idioma das instâncias do SAT que contêm variáveis , seja -SAT o idioma das instâncias do SAT nas quais todas as cláusulas têm no máximo k literais, e deixe k -SAT _v ser sua interseção. Seja s_k = \ inf_M \ {\ delta \ mid \ existe c \ forall v \; (M \ text {decide} k \ text {-SAT $ _v $ in} 2 ^ {v \ delta-c}) \ text { time}) \} , onde o mínimo varia sobre todos os algoritmos (máquinas em algum modelo de computação). Deixe s_ \ infty = \ lim_ {k \ to \ infty} s_ks ∞ = lim k → ∞ s k. Para que isso faça sentido, é necessário assumir que existe um limite razoável para o tamanho da entrada em termos do número de variáveis; caso contrário, pode-se repetir cláusulas para forçar e a serem tão grandes quanto desejado. Portanto, assuma que as cláusulas não são repetidas.
Observe que cada fórmula -CNF possui tamanho no máximo , portanto, o tamanho da fórmula de entrada não é importante quando se considera um expoente linear em . Segue-se que .
A hipótese de tempo exponencial (ETH) é a afirmação de que para alguns . A sequência aumenta infinitamente com frequência se ETH for válido. O forte ETH (SETH) é a declaração que ou , dependendo da referência usada.
Por outro lado, cada instância do SAT contém até cláusulas distintas (cada variável pode ser positiva, negativa ou ausente em cada cláusula). Portanto, uma entrada pode ter comprimento mesmo que nenhuma cláusula seja repetida; portanto, esse é um limite inferior para o tempo de leitura da entrada e também para o tempo total.
Se então permitirmos que , é claro que apenas considerando os tamanhos de entrada. Mesmo se alguém exigir que uma fórmula de entrada não contenha nenhuma cláusula incluída por outra, . Pelo algoritmo trivial, também é o caso de .s ω ≥ log 3 > 1,58 s ω ≥ 1,5 s ω ≤ 1 + log 3
Por que existe uma lacuna entre e , assumindo SETH?s ω
Em certo sentido, é apenas uma maneira diferente de atingir o limite, então parece intrigante que haja uma lacuna.
- Russell Impagliazzo e Ramamohan Paturi, Sobre a complexidade de SAT , JCSS 62 367–375, 2001. doi: 10.1006 / jcss.2000.1727 ( pré-impressão )
- Evgeny Dantsin e Alexander Wolpert, em tempo moderadamente exponencial para o SAT , SAT 2010, LNCS 6175 313–325. doi: 10.1007 / 978-3-642-14186-7_27 ( pré-impressão )
- Chris Calabro, Russell Impagliazzo e Ramamohan Paturi, A complexidade da satisfação de pequenos circuitos de profundidade , IWPEC 2009, LNCS 5917 75–85. doi: 10.1007 / 978-3-642-11269-0_6 ( pré-impressão )
- Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström, Em problemas tão difíceis quanto CNF-SAT , arXiv: 1112.2275v3 , 27 de março de 2014.
fonte