Schaefer's theorem and CSPs of unbounded width

Question

Schaefer's dichotomy theorem shows that each CSP problem over $\{0,1\}$ is either solvable in polynomial time or is NP-complete. This applies only for CSP problems of bounded width, excluding SAT and Horn-SAT, for example. General CSP problems of unbounded width may be very difficult (even uncomputable), so let's restrict ourselves to problems which are "natural" and are in NP.

Given a CSP problem of unbounded width, for each $k$, we can look at the restriction of the problem to clauses of width up to $k$. Schaefer's theorem now applies, and the restricted problem is either in P or NP-complete. If for some $k$, the $k$-restricted problem is NP-complete, then so is the unrestricted problem. The situation is less clear when for all $k$, the $k$-restricted problem is in P.

Schaefer's dichotomy theorem relies on four (or so) different algorithms that solve all the easy cases. Suppose that for a given CSP problem, the $k$-restricted problem is always solvable by algorithm A. It might be the case that algorithm A can be used to solve the unrestricted problem as well. Or it might be that algorithm A isn't polynomial time in the unrestricted case, and then we're ignorant as to the hardness of the problem.

Has this kind of problem been considered? Are there examples in which we arrive at the "ignorant" spot?

Answer 1

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:

1. Every relation in S (except for the constant 0) is satisfied by assigning 1 to all its variables.
2. Every relation in S (except for the constant 0) is satisfied by assigning 0 to all its variables.
3. Every relation in S is equivalent to a 2-CNF formula.
4. Every relation in S is equivalent to a Horn-clause formula.
5. 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.)
6. 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.