Log in

No account? Create an account
06 April 2008 @ 05:34 pm
Addressing NP-Complete Puzzles with Monte-Carlo Methods  
Maarten Schadd (with co-authors Mark Winands, Jaap van den Herik and Huib Aldewereld) gave a talk whose primary interest, from my POV, was that the bricks breaking game on Facebook is NP-Complete.

I'm going to have to explain that aren't I.

A P-time puzzle is one which, to all intents and purposes, can be solved quickly (according to a technical definition of quick). An NP-time puzzle is one in which, if you have the right answer, you can check it is right quickly but you can't necessarily find the right answer quickly. No one knows if P=NP though most people suspect not. Field medals will be won and a lot of research will get torn up if it turns out that P does equal NP.

I rather like bricks breaking.