> You're basically saying "Look at this polynomial problem and this other polynomial problem, if we combine them in a natural way, suddenly it becomes exponenti

> You're basically saying "Look at this polynomial problem and this other polynomial problem, if we combine them in a natural way, suddenly it becomes exponential?". My point is that your intuition is wrong. Yes, but that's not the only thing I am saying. Look more closely at what 2XSAT really is - it is basically a 2SAT transformed on an affine subspace of Z_2^n. You claimed that the complexity of 3SAT comes from 3 variables per clause, and not only two, as in 2SAT, but here I am showing an NP-complete class that has the same property as 2SAT! We can also restate 2XSAT reduction in this way - the only clause you need to have to be NP-complete is a clause that looks like (A XOR B) OR C (for arbitrary literals A,B,C). As you can notice, this clause already has the property of 2SAT clause (it forbids 2 combinations of A,B,C out of 8) rather than of 3SAT clause (which forbids 1 combination of A,B,C out of 8). I think you're actually assuming the conclusion, if you think that because something gives rise to "universal computation", then it must be difficult. But that's possibly silently assuming P!=NP. Still, the main point that 2XSAT reduction brings (at least to me) is that it hints that there is a clever generalization of both algorithms for 2SAT and XORSAT that runs in P (and if it doesn't, it will at least explain more clearly what the issue is). So that's my strategy, I am generalizing the proof of 2SAT to handle what I call generalized literals, XORs of any number of variables, i.e. linear equations, rather than simple literals. > Or you could have combined some different proportion of XOR clauses to the 2SAT instance to see how quickly it becomes intractable (or if it stays tractable). I don't understand this paragraph. I am not sure how I would measure whether a particular instance of 2XSAT is tractable or not. (I think they are all tractable, but I am still working on it.) I think the "hard" but satisfiable instances in 2XSAT have a really small dimension of affine subspace defined by XORSAT portion, and weak enough 2SAT portion to disallow all solutions. > FYI, there's a lot of work done for NP-Complete phase transitions. I am really not into phase transitions, but I think 2XSAT being NP-complete could explain them pretty nicely. I think most of the observed behavior comes from XORSAT portion dominating hard but satisfiable instances. AFAICT XORSAT exhibits similar phase transition, where there is only relatively small number of low-dimensional solutions to a random instance of XORSAT - either they have many solutions or the system becomes unsolvable. The only difficulty in analysing this is that 2SAT portion of 2XSAT, if it is dense enough, can also contribute to XORSAT portion (by forcing some variables to be constant or equal).