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 2025

S M T W T F S
1234567
8 9 1011 12 13 14
15 16 1718192021
22232425262728
2930     

Syndicate

RSS Atom

Tags

Style Credit

Expand Cut Tags

No cut tags