¿Hay instancias difíciles de 3-SAT cuando las cláusulas solo pueden usar literales que están "cerca" entre sí?

22

Deje que las variables sean . La distancia entre dos variables se define como. La distancia entre dos literales es la distancia entre las dos variables correspondientes. d ( x a , x b ) = | a - b |x1,x2,x3...xnd(xa,xb)=|ab|

Supongamos que tengo una instancia 3-SAT tal que para cada cláusula tenemos d ( x a , x b ) N d ( x a , x c ) N d ( x b , x c ) N para algún valor fijo N .(xa,xb,xc)d(xa,xb)Nd(xa,xc)Nd(xb,xc)NN

Conceptualmente, puede imaginar esto como todos los literales que están físicamente en una línea y todas las cláusulas son incapaces de llegar más allá de cierta longitud por razones físicas.

Dada esta restricción, ¿hay alguna instancia difícil de 3-SAT? ¿Qué tan pequeño puedo hacer el vecindario y aún encontrar instancias difíciles? ¿Qué sucede si permito que algunas cláusulas infrinjan la restricción?

Por duro quiero decir que un solucionador heurístico recurriría al peor de los casos.

IIAOPSW
fuente
2
"Por duro quiero decir que un solucionador heurístico recurriría al peor de los casos". no me suena bien definido. ¿Podemos interpretar su pregunta como si hubiera un algoritmo de tiempo polinómico que resuelva todas esas instancias de 3-SAT? ¿O preguntando sobre la complejidad / dureza de este problema?
DW
"¿Podemos interpretar su pregunta como si hay un algoritmo de tiempo polinómico que resuelva todas esas instancias de 3-SAT?" Creo que eso es lo que estoy buscando.
IIAOPSW
1
El requisito de localidad que está utilizando también se conoce como 1D "geométricamente local" y es el significado predominante de "localidad" para los físicos. Ahora, si uno generaliza su pregunta al caso cuántico y desde bits (2 estados) a partículas con 8 estados, la versión cuántica de su problema es de hecho QMA-complete ("quantum-NP") en 1D: Ver arxiv.org/ abs / 1312.1469 Para qubits, el problema es QMA completo en 2D. arxiv.org/abs/quant-ph/0504050
Martin Schwarz
44
Ah, entonces es cierto que un físico no puede esconderse entre los informáticos. Me atrapaste. ¿Por qué necesitas 8 estados? Simplemente use qubits, triplique el tamaño del vecindario y use cada 3 qubits para codificar una partícula de 8 estados.
IIAOPSW
1
Claro, pero entonces tienes una localidad bastante alta, es decir, tus operadores locales abarcan muchos qubits. Esta línea de investigación también se ha centrado en minimizar la localidad (idealmente 2-local) a costa de partículas dimensionales más altas y las compensaciones involucradas.
Martin Schwarz

Respuestas:

30

No. Si la instancia de 3-SAT tiene cláusulas , puede probar la satisfacción en el tiempo O ( m 2 N ) . Dado que N es una constante fija, este es un algoritmo de tiempo polinómico que resuelve todas las instancias de su problema.mO(m2N)N

El algoritmo funciona en etapas. Vamos φ i denotar la fórmula que consiste de las cláusulas que utilizan sólo las variables de x 1 , ... , x i . Supongamos que S i{ 0 , 1 } n denota el conjunto de asignaciones a x i - N , x i - N + 1 , ... , x i que puede extenderse a una asignación satisfactoria para φ i . Tenga en cuenta que dado Smφix1,,xiSi{0,1}nxiN,xiN+1,,xiφi , podemos calcular S i en el tiempoO( 2 N ): para cada( x i - N - 1 ,, x i - 1 ) S i - 1 , probamos ambas posibilidades para x i y verificamos si cumple todas las cláusulas de φ i que contienen la variable x i ; si es así, agregamos( x i - N ,...Si1SiO(2N)(xiN1,,xi1)Si1xiφixi a S i . En la i ésima etapa, calculamos S i . Una vez que hemos terminado todas lasetapas m , la instancia de 3-SAT es satisfactoria si y solo si S m . Cada etapa toma tiempo O ( 2 N ) , y hay m etapas, por lo que el tiempo total de ejecución es O ( m 2 N ) . Este es un polinomio en el tamaño de la entrada y, por lo tanto, constituye un algoritmo de tiempo polinomial.(xiN,,xi)SiiSimSmO(2N)mO(m2N)

Incluso si permite que un número fijo de cláusulas violen la restricción, el problema aún puede resolverse en tiempo polinómico. En particular, si cuenta el número de cláusulas que violan la restricción, puede resolver el problema en el tiempo O ( m 2 ( t + 1 ) N ) , enumerando primero todos los valores posibles para las variables en esas cláusulas, luego continúe con El algoritmo anterior. Cuando t es una constante fija, este es el tiempo polinómico. Puede haber algoritmos más eficientes.tO(m2(t+1)N)t

DW
fuente
16

El gráfico de incidentes de una fórmula SAT es un gráfico bipartito que tiene un vértice para cada cláusula y cada variable. Agregamos bordes entre una cláusula y todas sus variables. Si el gráfico de incidentes tiene un ancho de árbol limitado, entonces podemos decidir la fórmula SAT en P, en realidad podemos hacer mucho más. Su gráfico de incidentes es muy restringido. Por ejemplo, es un gráfico de ancho de ruta acotado, por lo que es solucionable en tiempo polinómico. Para el resultado estructural bien conocido anterior, por ejemplo, eche un vistazo a: https://www.sciencedirect.com/science/article/pii/S0166218X07004106 .

Saeed
fuente
1
En realidad, incluso el gráfico primario (un borde entre dos vértices si aparecen en la misma cláusula) tiene un ancho de ruta limitado en este caso. Vea también (1) que puede ser más accesible o la respuesta @DW, que es más o menos la misma idea que estos algoritmos. (1) Algoritmos para el conteo de modelos proposicionales , Marko Samer, Stefan Szeider, J. Algoritmos discretos, volumen 8, número 1, páginas 50-64, 2010.
holf