Afirmo que para un "CSP booleano natural", si la versión restringida de k está en P para cada k , entonces la versión no restringida también está en P. Definiré un "CSP booleano natural" a continuación.
El teorema de Schaefer establece que el CSP booleano en un conjunto finito S de relaciones está en P si se cumple al menos una de las siguientes condiciones y es NP-completa si ninguna de ellas se cumple:
- Cada relación en S (excepto la constante 0) se satisface asignando 1 a todas sus variables.
- Cada relación en S (excepto la constante 0) se satisface asignando 0 a todas sus variables.
- Cada relación en S es equivalente a una fórmula 2-CNF.
- Cada relación en S es equivalente a una fórmula de la cláusula Horn.
- Cada relación en S es equivalente a una fórmula de doble cláusula Horn. (Una "fórmula de cláusula de doble bocina" significa una fórmula CNF donde cada cláusula contiene como máximo un literal positivo).
- Toda relación en S es equivalente a una conjunción de cláusulas afines.
Ahora suponga que P ≠ NP, y considere el caso donde S es infinito. Si la versión restringida de k está en P para cada k , entonces, según el teorema de Schaefer, cada subconjunto finito de S satisface al menos una de las seis condiciones anteriores, y esto significa que todo el conjunto S satisface al menos una de las seis condiciones. ¿Significa esto que este CSP sin la restricción de arity también está en P? Aún no.
Cuando S es infinito, tenemos que especificar cómo se da cada cláusula en la fórmula de entrada. Suponemos que hay una cierta asignación de sobreyectiva {0,1} * a S , que especifica la codificación de las relaciones en S . Un CSP booleano se especifica dando tanto S como esta función de codificación.
Tenga en cuenta que en cada uno de los casos 3, 4, 5 y 6 anteriores, hay una forma natural de representar las relaciones que satisfacen la condición: una fórmula 2-CNF en el caso 3, una fórmula de la cláusula de Horn en el caso 4, y así sucesivamente. Incluso si una relación es equivalente a (digamos) una fórmula 2-CNF, no hay garantía a priori de que su codificación proporcione un acceso fácil a la fórmula 2-CNF que es equivalente a ella.
Ahora decimos que un CSP booleano es natural cuando su función de codificación satisface lo siguiente:
- Dada una codificación de una relación y una asignación a todas sus variables, si la relación se satisface o no se puede calcular en tiempo polinómico. (Nota: Esto asegura que el CSP en cuestión esté siempre en NP).
- Dada una codificación de una relación que satisface las condiciones 3, 4, 5 o 6, su representación natural como se especifica anteriormente se puede calcular en tiempo polinómico.
Entonces es fácil ver que si S satisface una de las seis condiciones anteriores y la codificación de S satisface esta condición de "naturalidad", entonces podemos aplicar el algoritmo correspondiente. La afirmación que dije al principio se puede probar considerando tanto el caso de P = NP como el caso de P ≠ NP.