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

July 2025

S M T W T F S
   12 3 4 5
6 7 89 1011 12
13 14 151617 1819
2021 22232425 26
27 28 293031  

Syndicate

RSS Atom

Tags

Style Credit

Expand Cut Tags

No cut tags