Friday, March 20, 2009

Dick Lipton's and Noam Nisan's Blogs

There are two new theory blogs.....
  • Dick Lipton's Gödel’s Lost Letter and P=NP : This is an awesome blog. During my first semester at GeorgiaTech I took Dick's course on 'Open Problems in CS theory'. What an excellent course that was !! In every class, Dick proposed at least three open problems along with possible ways to attack them and required references. Since, it was my first semester at Gatech, some of these problems intimidated me. Nevertheless, I maintained a special notebook and scribbled each and every problem and references he mentioned, hoping to revisit them later. I am gald that all his open problems are being documented in his blog.

Friday, March 13, 2009

Complexity of Ken Ken Game

I came across this puzzle named Ken Ken. It is Sudoku-type puzzle with arithmetic constraints. Here is a complexity question :
  • Is solving n x n Ken Ken puzzle NP-complete ?
NP-completeness results are known for similar games like Sudoku. Here is a paper on mathematics of Septoku. Here is David Eppstein's list of games with complexity results.