He visto cómo XOR-3-SAT se puede resolver de manera eficiente (por ejemplo, consulte la sección "Satisfacción de XOR" en la entrada de Wikipedia para el problema de satisfacción booleana ).
Me pregunto una pregunta básica: ¿es XOR-k-SAT eficientemente solucionable, para fórmulas con cantidades variables de literales por cláusula?
Realmente me gustaría saber si podemos aumentar la cantidad de literales por cláusula más allá de 3, y si podemos tener longitudes de cláusula mixtas.
complexity-theory
satisfiability
Matt Groff
fuente
fuente
Respuestas:
Parece que el artículo de Wikipedia al que se vinculó dice que XORSAT (no solo 3-XORSAT) está en P. El método por el cual están resolviendo esa fórmula de 3-XORSAT en su ejemplo se generaliza muy fácilmente a fórmulas en las que las cláusulas pueden tener arbitrariamente gran número de variables y diferentes números de variables.
Simplemente mira la fórmula como un sistema de ecuaciones lineales donde tiene una ecuación para cada cláusula y una variable para cada variable. Por ejemplo, la fórmula:
tiene una asignación satisfactoria si y solo si el siguiente sistema de ecuaciones tiene una solución:
¡Y podemos encontrar soluciones a sistemas lineales de ecuaciones como estas en tiempo polinómico usando la eliminación gaussiana!
fuente
Si. Es solucionable por eliminación gaussiana. La eliminación gaussiana puede resolver cualquier sistema de ecuaciones que sea un módulo lineal. XOR actúa como módulo de suma 2, por lo que cada cláusula XOR-SAT actúa como un módulo de ecuación lineal 2. En consecuencia, la eliminación gaussiana puede resolver cualquier fórmula XOR-k-SAT o cualquier fórmula XOR-SAT, incluso si hay un número variable de literales por cláusula o longitudes de cláusula mixta, en tiempo polinómico.
fuente