3 ms·
Wouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?
by mentater 4y ago
Wouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?
- xigoi 4y agoHow is it a solution to 3-SAT?
- HelloNurse 4y agoSAT complexity results from blowing up a reasonable number of variables/clauses (very rarely equivalent to others) in the formula to an enormous number of variable assignments (too many to store, and having only three classes, formula true or false or not evaluated so far, that are not useful equivalencies). What disjoint sets are you thinking of tracking?
- jcranmer 4y agoI think I understand why you're confused here. To the extent that union-find is similar to SAT, it's similar to 2-SAT: the constraints you're reasoning about are defined only on pairs of elements, whereas 3-SAT is fundamentally reasoning about triplets (at least one of these three variables is true). Notably, 2-SAT is a variant of SAT that is polynomial in time, unlike 3-SAT.