K-XORSAT es el problema de decidir si una fórmula booleana $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ es satisfactoria. Aquí $\oplus$ denota el binario XOR operación, $I$ es un conjunto de índices, y cada cláusula tiene $k$ literales distintos $l_{s_{ij}}$ cada una de las cuales es una variable $x_{s_{ij}}$ o su negación.
Equivalentemente, $k$ -XORSAT requiere decidir si un conjunto de ecuaciones lineales, cada una de la forma $\sum_{j=1}^k x_{s_{ij}}\equiv 1\; (\mod 2)$ tiene una solución sobre $\mathbb{Z}_2 = \mathbb{Z}/2\mathbb{Z}$ .
Todo problema de decisión Q tiene asociado un problema de recuento #Q, que (informalmente hablando) requiere establecer el número de soluciones distintas. Estos problemas de recuento forman la clase de complejidad #P . Los problemas "más difíciles" de #P son #P-completos, ya que cualquier problema de #P puede reducirse a un problema #P-completo.
El problema de recuento asociado a cualquier problema de decisión NP-completo es #P-completo. Sin embargo, muchos problemas de decisión "fáciles" (algunos incluso resolubles en tiempo lineal) también conducen a problemas de recuento #P-completos. Por ejemplo, el artículo original de Leslie Valiant de 1979 La complejidad de calcular lo permanente muestra que calcular la permanente de una matriz 0-1 es #P-completo. Como segundo ejemplo, la lista de problemas #P-completos del artículo complementario La complejidad de los problemas de enumeración y fiabilidad incluye #MONOTONE 2-SAT; este problema requiere contar el número de soluciones a fórmulas booleanas en forma normal conjuntiva, donde cada cláusula tiene dos variables y no se permiten variables negadas. (MONOTONE 2-SAT es, por supuesto, bastante trivial como problema de decisión).
Andrea Montanari ha escrito sobre la función de partición de $k$ -XORSAT en algunos notas de clase y, al parecer, su libro con Marc Mézard habla de ello (por desgracia, no dispongo de un ejemplar, y el capítulo 17 correspondiente no figura en el borrador en línea de Montanari).
Estas consideraciones conducen a la siguiente pregunta:
Es # $k$ -XORSAT #¿P-completo?
Nótese que la fórmula de las notas de Montanari no parece responder obviamente a esta pregunta. El hecho de que exista una buena solución de forma cerrada no significa que podamos evaluarla de forma eficiente: consideremos la fórmula Todos los polinomios .
Algunos problemas de recuento difíciles en #P aún pueden aproximarse en cierto sentido, mediante un esquema denominado FPRAS. Jerrum, Sinclair y colaboradores han relacionado la existencia de un FPRAS para problemas #P con la cuestión de si $NP = RP$ . Por lo tanto, también me interesaría la pregunta subsidiaria
Hace $k$ -¿XORSAT dispone de un FPRAS?
Edición: aclarada la segunda pregunta según el comentario de Tsuyoshi Ito. Tenga en cuenta que la respuesta de Peter Shor hace que esta parte de la pregunta sea discutible.
