Deje que SAT sea el lenguaje de esas instancias de SAT que contienen variables , deje que -SAT sea el lenguaje de esas instancias de SAT en las que cada cláusula tiene a lo sumo literales, y deje que -SAT sea su intersección. Deje , donde el rango infimum abarca todos los algoritmos (máquinas en algún modelo de computación). Deje s_ \ infty = \ lim_ {k \ to \ infty} s_ks ∞ = lim k → ∞ s k. Para que esto tenga sentido, uno tiene que suponer que hay un límite razonable en el tamaño de la entrada en términos del número de variables; de lo contrario, se podrían repetir cláusulas para forzar que y sean tan grandes como se desee. Por lo tanto, suponga que las cláusulas no se repiten.
Tenga en cuenta que cada fórmula -CNF tiene un tamaño como máximo de , por lo que el tamaño de la fórmula de entrada no es importante cuando se considera un exponente que es lineal en . Luego se deduce que .
La hipótesis de tiempo exponencial (ETH) es la afirmación de que para algunos . La secuencia aumenta infinitamente si ETH se mantiene. El Strong ETH (SETH) es la afirmación de que o , dependiendo de la referencia que se use.
En contraste, cada instancia de SAT contiene hasta cláusulas distintas (cada variable puede ser positiva, negativa o ausente en cada cláusula). Por lo tanto, una entrada puede tener una longitud incluso si no se repite ninguna cláusula, por lo que este es un límite inferior para el tiempo para leer la entrada, y luego también para el tiempo general.
Si entonces dejamos que , está claro que simplemente considerando los tamaños de entrada. Incluso si uno requiere una fórmula de entrada que no contenga ninguna cláusula subsumida por otra, . Por el algoritmo trivial, también es el caso de que .s ω ≥ log 3 > 1.58 s ω ≥ 1.5 s ω ≤ 1 + log 3
¿Por qué hay una brecha entre y , suponiendo SETH?s ω
En cierto sentido, es solo una forma diferente de tomar el límite, por lo que parece desconcertante que debería haber una brecha.
- Russell Impagliazzo y Ramamohan Paturi, Sobre la complejidad de -SAT , JCSS 62 367–375, 2001. doi: 10.1006 / jcss.2000.1727 ( preprint )
- Evgeny Dantsin y Alexander Wolpert, Sobre tiempo moderadamente exponencial para SAT , SAT 2010, LNCS 6175 313–325. doi: 10.1007 / 978-3-642-14186-7_27 ( preimpresión )
- Chris Calabro, Russell Impagliazzo y Ramamohan Paturi, The Complexity of Satisfiability of Small Depth Circuits , IWPEC 2009, LNCS 5917 75–85. doi: 10.1007 / 978-3-642-11269-0_6 ( preimpresión )
- Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström, Sobre problemas tan difíciles como CNF-SAT , arXiv: 1112.2275v3 , 27 de marzo de 2014.
fuente