Q:

General structure of solutions to 3-SAT circuits

Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any three solutions to an XOR-SAT circuit, their bitwise XOR is also a solution. Lastly, given any two solutions to a HORN-SAT circuit, their bitwise AND is also a solution.
Does there exist a similar situation for 3-SAT, where given some subset of solutions, one can somehow generate additional solutions?
If not, does there exist a related SAT problem that 3-SAT can be reduced to, and hence which is also NP-complete, which have solutions of the form specified? For instance 1-in-3 SAT, or exactly-3-SAT, or NAE-3-SAT, or etc.

A:

The theory you are after is universal algebra. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s dichotomy theorem, which was recently extended to arbitrary alphabets.
3SAT has no polymorphisms. NAE-3SAT has only negation as a polymorphism. All other classes of polymorphisms correspond to CSPs solvable in polynomial time. See Allender et al., The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem.

