News for hackers. Stuff that matters.
Re:The Prolog Story by pdany on Thursday May 20, 2010 @05:26PM (#1365471)
Well a lot of prolog implementations also feature finite domain and rational domain solvers, global constrains that I don't think your 15 year old buddies would be able to code in an hour.

Having said that, most problems we solve here are NP-Complete, most of the time the trivial pruning you are mentioning does not really extend the limits for the computation.

Re:The Prolog Story by barrkel on Thursday May 20, 2010 @05:38PM (#1365521)
For sure, I was speaking in the context of the packing problems, and even simpler discrete combinatorial problems, which really are pretty simple. But I wouldn't dismiss trivial pruning lightly; many problems can have their search branches pruned early based on their costs exceeding the current best solution, and as that solution gets better, it will start pruning higher up the search tree.

The knapsack problem, as you know, is NP-Complete.