I claim that for a “natural Boolean CSP,” if the k-restricted version is in P for every k, then the unrestricted version is also in P. I will define a “natural Boolean CSP” below.
Schaefer’s theorem states that the Boolean CSP on a finite set S of relations is in P if at least one of the following conditions is satisfied and it is NP-complete if none of them is satisfied:
- Every relation in S (except for the constant 0) is satisfied by assigning 1 to all its variables.
- Every relation in S (except for the constant 0) is satisfied by assigning 0 to all its variables.
- Every relation in S is equivalent to a 2-CNF formula.
- Every relation in S is equivalent to a Horn-clause formula.
- Every relation in S is equivalent to a dual-Horn-clause formula. (A “dual-Horn-clause formula” means a CNF formula where each clause contains at most one positive literal.)
- Every relation in S is equivalent to a conjunction of affine clauses.
Now assume that P≠NP, and consider the case where S is infinite. If the k-restricted version is in P for every k, then by Schaefer’s theorem, every finite subset of S satisfies at least one of the six conditions above, and this means that the whole set S satisfies at least one of the six conditions. Does this mean that this CSP without the restriction on arity is also in P? Not yet.
When S is infinite, we have to specify how each clause in the input formula is given. We assume that there is some surjective mapping from {0,1}* to S, which specifies the encoding of the relations in S. A Boolean CSP is specified by giving both S and this encoding function.
Note that in each of cases 3, 4, 5, and 6 above, there is a natural way to represent relations satisfying the condition: a 2-CNF formula in case 3, a Horn-clause formula in case 4, and so on. Even if a relation is equivalent to (say) a 2-CNF formula, there is no a priori guarantee that its encoding gives an easy access to the 2-CNF formula which is equivalent to it.
Now we say that a Boolean CSP is natural when its encoding function satisfies the following:
- Given an encoding of a relation and an assignment to all its variables, whether the relation is satisfied or not can be computed in polynomial time. (Note: This ensures that the CSP in question is always in NP.)
- Given an encoding of a relation satisfying condition 3, 4, 5, or 6, its natural representation as specified above can be computed in polynomial time.
Then it is easy to see that if S satisfies one of the six conditions above and the encoding for S satisfies this “naturalness” condition, then we can apply the corresponding algorithm. The claim which I stated at the beginning can be proved by considering both the case of P=NP and the case of P≠NP.