5 ms·
I’m not sure the comparison to SAT is a good one because, in that case, we know of particular “phase transition” regions in which most problems aren’t clearly s
by SilasX 3y ago
I’m not sure the comparison to SAT is a good one because, in that case, we know of particular “phase transition” regions in which most problems aren’t clearly satisfiable or unsatisfiable. (Specifically, when the ratio of clauses to variables in 3SAT is about 4.2.)
- oldgradstudent 3y agoIt's an excellent comparison to SAT, because in both cases nobody cares about random instances at all. For non-random instances the ratio of clauses to variables in is utterly meaningless.