Open thread, July 16-22, 2013

David_Gerard

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

Given the discussion thread about these, let's try calling this a one-week thread, and see if anyone bothers starting one next Monday.

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

Given the discussion thread about these, let's try calling this a one-week thread, and see if anyone bothers starting one next Monday.

Another day, another (controversial) opinion!

http://protokol2020.wordpress.com/2013/07/17/is-p-np/

I think this misunderstands the state of modern complexity theory.

There are lots of NP-complete problems that are well known to have highly accurate approximations that can be computed efficiently. The knapsack problem and traveling-salesperson in 2D Euclidean space are both examples of this. Unfortunately, having an epsilon-close approximation for one NP-complete problem doesn't necessarily help you on other NP-complete problems.

There's nothing particularly magic about evolutionary algorithms here. Any sensible local search will often work well on instances of NP-complete problems.

4David_Gerard13y

Confuses analytical best solution (what P=NP would be) with numerical good-enough solution (what evolution approximates just well enough to get advantage).

23

Open thread, July 16-22, 2013

23

23

23

Open thread, July 16-22, 2013

23

23