purplecat

You're viewing

purplecat's journal
Create a Dreamwidth Account Learn More

Reload page in style: light

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

October 2017

S	M	T	W	T	F	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Syndicate

Tags

100 papers [9]
academia [77]
- ai [4]
  - ethics [2]
- dead scientists [2]
- edinburgh informatics [3]
- grants [1]
- groups
  - dream [2]
- impact [1]
- public understanding [27]
  - lego rover [19]
- publications [33]
- scientists
  - aaron sloman [1]
  - alan bundy [4]
  - douglas hofstadter [1]
  - john mccarthy [2]
- talks [23]
- teaching [1]
academic
- public understanding
  - lego rover [1]
administrivia [1]
agents of shield [1]
ai [19]
- agents [22]
  - ail [9]
  - bdi [10]
    - goals [1]
  - groups [3]
  - languages
    - agentspeak [2]
      - jason [1]
    - oopl [1]
  - organisations [3]
- automated reasoning [7]
  - rippling [1]
  - sat [1]
  - smt [1]
- hybrid systems [1]
- knowledge representation [1]
- planning [1]
- robotics [1]
aisb [10]
amazon [1]
anecdote [1]
arthuriana [6]
bernice summerfield [7]
- review [6]
birthday [11]
books [57]
- author
  - andrew cartmel [3]
  - ben aaronovitch [4]
  - c s lewis [2]
  - charlotte bronte [2]
  - craig hinton [2]
  - david mcintee [1]
  - dorothy l sayers [2]
  - iain m banks [3]
  - iain rankin [1]
  - ian rankin [2]
  - j r r tolkien [2]
  - jacqueline rayner [2]
  - jane austen [2]
  - jeff vandermeer [2]
  - jim mortimore [1]
  - jonathan blum [2]
  - justin richards [3]
  - kate orman [2]
  - kelly hale [1]
  - lance parkin [2]
  - lawrence miles [6]
  - mags halliday [6]
  - malcolm hulke [2]
  - marc platt [2]
  - mark michalowski [4]
  - mary stewart [2]
  - megan whalen turner [3]
  - michael moorcock [2]
  - neal stephenson [4]
  - paul cornell [4]
  - paul dale smith [5]
  - paul magrs [12]
  - philip purser-hallard [10]
  - phyllis ann karr [2]
  - rob shearman [1]
  - rosemary sutcliff [3]
  - sara paretskey [2]
  - shakespeare [1]
  - simon guerrier [2]
  - terrance dicks [3]
  - terry pratchett [2]
  - tolkien [3]
- review [25]
castle [1]
christmas [1]
class [7]
- review [7]
computer science [15]
- complexity theory [4]
- game theory [5]
  - economics [1]
- np problems [1]
- verification [3]
  - induction [1]
conferences [3]
- aamas [1]
- arw [1]
- clima [1]
- picspam [1]
conventions [6]
- eastercon [10]
  - 2010 [2]
  - 2011 [4]
  - 2012 [1]
  - 2015 [1]
- lass o gowrie [1]
crochet [30]
- amigurumi [9]
- garment [4]
- non-euclidean [10]
current affairs [18]
current events [9]
diary [7]
doctor who [349]
- author
  - andrew cartmel [3]
  - ben aaronovitch [2]
  - craig hinton [2]
  - david mcintee [1]
  - david whittaker [1]
  - jim mortimore [1]
  - jonathan blum [1]
  - justin richards [3]
  - kate orman [2]
  - kelly hale [1]
  - lance parkin [3]
  - lawrence miles [5]
  - mags halliday [6]
  - malcolm hulke [2]
  - marc platt [2]
  - mark michalowski [4]
  - paul cornell [3]
  - paul dale smith [3]
  - paul magrs [8]
  - philip purser-hallard [8]
  - rob shearman [3]
  - terrance dicks [3]
- books [32]
  - edas [2]
  - nas [4]
  - new series [10]
  - non-fiction [2]
  - pdas [1]
  - review [28]
  - short trips [3]
  - time and relative disse [5]
- fandom [3]
- new series [7]
- nuwho rewatch [72]
- rec [1]
- review [321]
  - book [34]
    - non-fiction [4]
  - film [1]
  - tv [295]
    - classic [85]
    - new series [208]
- russell davies [3]
- steven moffat [2]
- the randomizer [89]
- verity podcast [1]
dreamwidth [3]
edinburgh [7]
- festival [1]
exercise [2]
- running [12]
facebook [5]
faction paradox [3]
- review [3]
family [8]
- b [21]
  - animals [1]
  - dinosaurs [15]
  - fossils [2]
  - media stardom [18]
- cousins [1]
- g [4]
  - school [1]
fandom [2]
fandom friday [2]
fanfiction [3]
feminism [5]
films [8]
- review [4]
follow friday [6]
food [13]
- heston blumenthal [1]
- recipe [3]
fools and heroes [11]
fossil friday [4]
friends [2]
genealogy [14]
history [3]
holidays [2]
- hadrian's wall [12]
house [16]
i have no tag for this [23]
i saw this last week [26]
iris wildthyme [6]
- review [5]
jobs [3]
kin-strife [10]
linkspam [18]
livejournal [13]
lizzie bennet diaries [1]
mathematics [21]
- formal proof [1]
- logic [1]
- non-euclidean [10]
- philosophy [6]
  - proof [2]
- quote [1]
- verification [1]
mcu [1]
media stardom [4]
meme [32]
meta [1]
model checking [4]
- systems
  - java pathfinder [3]
oxford [1]
performing [1]
- music [1]
philosophy [8]
- ai [2]
- ethics [1]
- mathematics [3]
picspam [41]
- house [2]
- travel [26]
  - holidays [5]
  - work related [16]
primeval [50]
- review [44]
programming [13]
- ail [1]
- languages
  - agentspeak [2]
    - jason [1]
  - java [5]
  - maude [2]
  - prolog [2]
projects
- eass [13]
  - publications [7]
- mcapl [13]
  - publications [5]
- platform grant [1]
- rais [2]
  - publications [2]
- verifiable autonomy [1]
  - publication [1]
- vps [2]
  - publications [2]
publications [8]
random doctor who picture [40]
random poetry [1]
rant [6]
reading listening watching [30]
rec [1]
- humour [1]
resolutions [14]
revew [3]
review [503]
- book [138]
  - bernice summerfield [5]
  - doctor who [37]
    - non-fiction [5]
  - non-fiction [39]
    - history [25]
      - science [9]
- comic [2]
- doctor who [301]
  - book [22]
  - film [1]
  - tv [285]
- film [10]
- tv [354]
  - class [7]
  - doctor who [275]
  - internet [1]
  - merlin [2]
  - primeval [45]
  - sarah jane adventures [5]
  - survivors [4]
  - torchwood [13]
roleplaying [22]
ros [1]
science [1]
science fiction [2]
science
- astronomy [1]
  - apod [1]
share
- twitter [2]
social networking [3]
- google+ [2]
- tumblr [1]
star wars [1]
theorem proving [6]
- middle-out reasoning [3]
- proof planning [5]
  - critics [2]
  - rippling [3]
- proof specification lang [2]
- systems
  - isabelle [2]
  - isaplanner [4]
  - maude [1]
  - proof general [3]
- theory slicing [1]
- tptp thf [3]
throwback thursday [16]
tolkienery [4]
travel [33]
- commuting [2]
- holidays [4]
- work related [28]
traveller [6]
tv [11]
- blakes seven [1]
- class [1]
  - review [1]
- firefly [2]
- sapphire and steel [1]
- special unit 2 [1]
- supernatural [1]
- torchwood [5]
urban dead [5]
web stuff [2]
wierd spam [2]
writing [2]

Page Summary

Addressing NP-Complete Puzzles with Monte-Carlo Methods

Active Entries

Style Credit

Base style: Transmogrified by Yvonne
Theme: Sleeping Warrior by dancing_serpent

Expand Cut Tags

No cut tags

Top of page

Addressing NP-Complete Puzzles with Monte-Carlo Methods