3 ms·
> I was under the impression that all NP-Complete problems take O(n!). SAT is NP-complete and the naive algorithm ("just try every combination") is O(2^n). Eve
by muldvarp 3y ago
> I was under the impression that all NP-Complete problems take O(n!).
SAT is NP-complete and the naive algorithm ("just try every combination") is O(2^n). Even for TSP there is a dynamic programming approach that takes O(n^2*2^n) instead of O(n!).