Vaniver comments on Tiling Agents for Self-Modifying AI (OPFAI #2) - Less Wrong

55 Post author: Eliezer_Yudkowsky 06 June 2013 08:24PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (260)

You are viewing a single comment's thread. Show more comments above.

Comment author: Vaniver 01 July 2013 10:09:28PM 4 points [-]

You can't do that? From random things like computer security papers, I was under the impression that you could do just that - convert any NP problem to a SAT instance and toss it at a high-performance commodity SAT solver with all its heuristics and tricks, and get an answer back.

You can do this. Minor caveat: this works for overall heuristic methods- like "tabu search" or "GRASP"- but many of the actual implementations you would see in the business world are tuned to the structure of the probable solution space. One of the traveling salesman problem solvers I wrote a while back would automatically discover groups of cities and move them around as a single unit- useful when there are noticeable clusters in the space of cities, not useful when there aren't. Those can lead to dramatic speedups (or final solutions that are dramatically closer to the optimal solution) but I don't think they translate well across reformulations of the problem.