Re:Ask HN: What are some cool but obscure data structures yo...
by mentater on Friday July 22, 2022 @02:04AM
(#32189026)
Wouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?
[ Parent
| on HN ]
Re:Ask HN: What are some cool but obscure data structures yo...
by jcranmer on Friday July 22, 2022 @04:26PM
(#32196720)
I 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.
Re:Ask HN: What are some cool but obscure data structures yo...
by HelloNurse on Friday July 22, 2022 @04:57AM
(#32189992)
SAT 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?