4 ms·
The entire space of "NP-complete techniques" is very interesting to me. At some point, you will come across an NP-complete problem, and your only choices are to
by dragontamer 4y ago
The entire space of "NP-complete techniques" is very interesting to me. At some point, you will come across an NP-complete problem, and your only choices are to either give up, or try your best to solve the problem anyway.
Constraint Programming "clicks" for me a lot more than SAT solvers, which feel more mystical. BDDs and MDDs also deserve a mention, as BDDs kinda solve the #P-complete problem (counting-NP complete problem: not only finding one valid solution, but the count of all valid solutions to an NP complete situation. Many optimization problems are #P complete, as you want to iterate over all of the valid solutions and find the best one.
- cerved 4y agoConstraint programming is very elegant but metaheuristic approaches often scale much better than a traditional CP approach. Constraint based Lucas search, CBLS, is an interesting fusion