3 ms·

> In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's

by js8 3y ago

> In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's easy to do arbitrary computation. I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. > To my eyes, if this can be short-circuited, it's essentially saying that for arbitrary functions, there's no actual reason to do computation as it can be short-circuited. In other words, you're saying one can do better than raw simulation in every single case. While potentially true, it seems like a pretty bold statement. I don't think that's what P=NP would imply. Remember, if P=NP, the algorithm is polynomial in the worst case, it can still be true that for a portion (even a majority) of actual instances, the simulation is faster than applying the algorithm. (Also it's possible that for some instances, functions that already have been properly "inverted", the decision algorithm and the simulation are equivalent, this is similar to linear equations, once you have factorized the matrix to the upper echelon form, then application of the matrix is the same process as solving it.) What the result will say that you don't need to be exponential in the worst case.

abetusk 3y ago
> I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. XORSAT is not NP-Complete because a chain of XOR boolean functions can't be chained to create arbitrary computation. 2SAT is restrictive because, even though it has a "fundamental" gate (NAND/NOR), the "splay" of variable interaction is so limited. In some sense, 2SAT and XORSAT, each individually, are conspiring to prevent general purpose computation. > I don't think that's what P=NP would imply. ... What the result will say that you don't need to be exponential in the worst case. If P=NP, then the program I listed above can be short circuited from exponential search to polynomial.
- js8 3y ago
  I don't think you understand. Sure, 2SAT and XORSAT are, in isolation, too weak to be NP-complete. However, if you combine them, and allow for both types of clauses in the same instance (on a common set of variables), then surprisingly it is NP-complete (I call that class 2XSAT), by reduction from 3SAT. This is, to my knowledge, a previously unknown reduction and the reason why I now strongly believe that P=NP.
  - abetusk 3y ago
    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.

by js8 3y ago

abetusk 3y ago

> I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. XORSAT is not NP-Complete because a chain of XOR boolean functions can't be chained to create arbitrary computation. 2SAT is restrictive because, even though it has a "fundamental" gate (NAND/NOR), the "splay" of variable interaction is so limited. In some sense, 2SAT and XORSAT, each individually, are conspiring to prevent general purpose computation. > I don't think that's what P=NP would imply. ... What the result will say that you don't need to be exponential in the worst case. If P=NP, then the program I listed above can be short circuited from exponential search to polynomial.

js8 3y ago
I don't think you understand. Sure, 2SAT and XORSAT are, in isolation, too weak to be NP-complete. However, if you combine them, and allow for both types of clauses in the same instance (on a common set of variables), then surprisingly it is NP-complete (I call that class 2XSAT), by reduction from 3SAT. This is, to my knowledge, a previously unknown reduction and the reason why I now strongly believe that P=NP.
- abetusk 3y ago
  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.