4 ms·
They did. Reduced it from a NP-class problem (IIRC dependencies constraint solving required a SAT solver) to mere tree traversal.
by sansnomme 7y ago
They did. Reduced it from a NP-class problem (IIRC dependencies constraint solving required a SAT solver) to mere tree traversal.
- ameliaquining 7y agoI think it's still NP-complete because you can still specify arbitrary dependency constraints. (Of course, just because it's NP-complete doesn't mean it's not tractable in practice for the kinds of instances that come up in real life.)