purplecat: Hand Drawn picture of a Toy Cat (aisb)
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.

Profile

purplecat: Hand Drawn picture of a Toy Cat (Default)
purplecat

August 2017

S M T W T F S
   1 2 3 4 5
67 89101112
13 1415161718 19
20212223242526
2728293031  

Syndicate

RSS Atom

Tags

Style Credit

Expand Cut Tags

No cut tags