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

June 2017

S M T W T F S
    123
45678 9 10
11 12 13 14 1516 17
18 19 20 21222324
252627282930 

Syndicate

RSS Atom

Tags

Style Credit

Expand Cut Tags

No cut tags