Cuestiones de aplicación en 2-satisfacibilidad problema

Question

Quiero poner en práctica el problema 2-SAT 100000 literales. Para que no hubiera 200000 vértices. Así que estoy atascado en tener un conjunto de todos los vértices alcanzables desde cada vértice, la complejidad del espacio O(200000^2) que es inviable Así que por favor sugerir una solución para esto. Y por favor, arrojar alguna luz sobre la aplicación eficiente de los problemas 2-SAT.

Answer 1

Wikipedia :

  

... 2-satisfacibilidad puede ser resuelto en tiempo polinómico. Como Aspvall, Plass y Tarjan (1979) observaron, una instancia de 2-satisfacibilidad es resoluble si y sólo si todas las variables de la instancia pertenece a un componente fuertemente conectado diferente de la gráfica implicación de la negación de la misma variable. Puesto que los componentes fuertemente conectados se pueden encontrar en el tiempo lineal por un algoritmo basado en la profundidad primera búsqueda, al mismo tiempo lineal unido aplica también a 2-satisfacibilidad.

No voy a pretender entender la mayor parte de ese párrafo, pero parece que hay es un algoritmo que puede ser utilizado para resolver el problema 2-SAT, y se describe dentro de esa referencia documento ( a algoritmo de tiempo lineal para probar la verdad de ciertas fórmulas booleanas cuantificados ). Al parecer, se pueden comprar en línea por alrededor de $ 20 USD. No estoy seguro de si eso es útil o no, pero ahí está!

actualización: Un PDF libre del mismo documento se puede encontrar aquí . El crédito va a Liori para el hallazgo.

Answer 2

Todo este hilo es un poco en mal estado. Sí, se puede resolver 2-sat en el tiempo lineal, pero no - no se puede solucionarlo para que muchas variables. El tiempo para resolver 2-sat es lineal con respecto al número de la implicación, que por 200 000 variables que podrían alcanzar hasta (200000 * 199999) / 2 y, además, si se utiliza esta solución, necesitará aproximadamente la misma cantidad de memoria . Hay otra solución (no usar componentes fuertemente vinculados que sea más lento, pero no es necesario que la cantidad de memoria).