4 ms·

Yes, I think I understand, both why you believe P=NP and what the 2XSAT construction is. You're basically saying "Look at this polynomial problem and this othe

Yes, I think I understand, both why you believe P=NP and what the 2XSAT construction is. 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. For example, XOR by itself is not Turing machine equivalent, nor is NOT, nor is AND and OR by themselves, but combine some subset and suddenly you get NAND, NOR etc. which gives arbitrary computation. One of the interpretations of the Halting Problem is that one can do no better than raw simulation. The intuition, by extension, is that for NP-Complete problems, one can also do no better than raw simulation (search the space for solutions). If we could do better than simulation, if there were a "short circuit" to the computation, then the program I listed above, which looks suspiciously like running arbitrary program with some time and space bounds, would not need to run in exponential time. Arbitrary computation is the norm, not the exception. 2SAT and XORSAT are the exception because of their restrictions putting them in polynomial time and their inability to do arbitrary computation. If their fragility is disturbed, even by adding just a whiff of freedom in the form of more gates or arrangement, then they suddenly allow for arbitrary computation. You believe your addition is just a slight nudge so the topple to arbitrary computation and, potentially, exponential time seems drastic, but you have a bias on what's "natural". For example, you could have decided to add some portion of 3 variable clauses to the 2SAT instance to see how quickly it blows up (if at all). 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). Which is more natural? Which is the smaller nudge? Why is your nudge not a shove? FYI, there's a lot of work done for NP-Complete phase transitions. When I said this is poorly understood, I mean it. For all intents and purposes, "random" 3SAT (each clause chooses which variable uniformly at random, with equal probability of being negated) is, for all intents and purposes, solvable, even for millions of variables. As far as I know, there isn't a good proposal or understanding for a "natural" and "random" 3SAT ensemble that remains difficult as the scale increases.

js8 3y ago
> 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).

js8 3y ago

> 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).