ETH: k-SAT vs SAT?

8

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_kv[v]={0 0,1,...,v-1}kkkvs = lim k s ksk=infMETRO{δCv(METRO decide k-SE SENTÓv en 2vδ-C) hora)}s=limksk. 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 sk y s sean tan grandes como se desee. Por lo tanto, suponga que las cláusulas no se repiten.

Tenga en cuenta que cada fórmula k -CNF tiene un tamaño como máximo de O(vk) , por lo que el tamaño de la fórmula de entrada no es importante cuando se considera un exponente que es lineal en v . Luego se deduce que s3s4 4s .

La hipótesis de tiempo exponencial (ETH) es la afirmación de que sk>0 0 para algunos k3 . La secuencia (sk) aumenta infinitamente si ETH se mantiene. El Strong ETH (SETH) es la afirmación de que s1 o s=1 , dependiendo de la referencia que se use.

En contraste, cada instancia de SAT v contiene hasta 3v cláusulas distintas (cada variable puede ser positiva, negativa o ausente en cada cláusula). Por lo tanto, una entrada puede tener una longitud Ω(2norteIniciar sesión3) 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 3sω=infMETRO{δCv(METRO decide SE SENTÓv en 2vδ-C) hora)}sωIniciar sesión3>1,58sω1,5sω1+Iniciar sesión3

¿Por qué hay una brecha entre y , suponiendo SETH?s ωssω

En cierto sentido, es solo una forma diferente de tomar el límite, por lo que parece desconcertante que debería haber una brecha.sω

  • Russell Impagliazzo y Ramamohan Paturi, Sobre la complejidad de -SATk , 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.
András Salamon
fuente

Respuestas:

6

La diferencia entre sus definiciones es que el ancho de la cláusula en puede crecer con el número de variables, mientras que para es arbitrariamente grande pero constante.s sωs

Es un problema similar a PH vs PSPACE. Si toma un número constante arbitrario de alteraciones del cuantificador, obtiene la jerarquía polinómica, pero si permite que la fórmula se cuantifique completamente, obtendrá un problema de PSPACE completo.

Stefan Schneider
fuente
4

Una mejor manera de definir estos exponentes es si pregunta sobre el tiempo de ejecución en la forma , donde es un polinomio arbitrario del tamaño de entrada. Luego desaparecen los artefactos como el tamaño .Cnortepagsoly(El |FEl |)pagsoly(El |FEl |)3v

Hirsch
fuente
Parece un enfoque sensato motivado por la complejidad parametrizada. Sin embargo, los documentos que tratan sobre ETH parecen dejarlo bastante vago o utilizan una definición que es esencialmente la que proporcioné anteriormente. ¿Tienes un puntero?
András Salamon
Cuando hablamos de k-SAT, no importa, porque el tamaño de la fórmula es polinomial en el número de variables. Con respecto a los punteros, observe, por ejemplo, cómo Impagliazzo, Paturi y Zane definen la clase SE en "¿Qué problemas tienen una complejidad exponencial fuerte?", Journal of Computer and System Sciences 63, 512-530 (2001).
hirsch
Gracias, eso es útil; Anteriormente solo me he centrado realmente en el Lema de Sparsificación de ese documento.
András Salamon