You're reading: News

Deriving dynamical equations is NP-Hard

This paper has just been accepted by Physical Review Letters:

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this work, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP-hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).

This paper has been accepted, so I can’t see why I shouldn’t be able to read it yet. Possibly something to do with money. The preprint is on the ArXiv, anyway.

via ScienceNOW via Slashdot, who reported it as “It’s Official: Physics is Hard”. That’s exactly the kind of unhelpful attention-grabbing headline we’re hoping to avoid here at The Aperiodical.

A commenter on Slashdot raises an interesting point:

Could we then map NP-HARD computation problems onto real world physics systems to find solutions?

Pricing bot interactions

Carlos Bueno writes about a book “Computer Game Bot Turing Test”. This, he says, is:

one of over 100,000 “books” “written” by a Markov chain running over random Wikipedia articles, bundled up and sold online for a ridiculous price. The publisher, Betascript, is notorious for this kind of thing.

He writes that the pricing bots on Amazon Marketplace have got hold of this book and are “fight epic price wars” over it.

So with “Turing Test” we have a delightful futuristic absurdity: a computer program, pretending to be human, hawking a book about computers pretending to be human, while other computer programs pretend to have used copies of it. A book that was never actually written, much less printed and read.

He then talks about his own book (Lauren Ipsum; a children’s story about computer science) and how he saw pricing bots fighting over this. The book is print-on-demand, so a bot claiming to have a used copy could simply buy a new copy and resell it for a profit. Then the bots started to undercut the retail price! Finally, the Amazon pricing bot put his book on sale at 28% discount (and Amazon swallows the difference).

My reaction to this algorithmic whipsawing has settled down to a kind of helpless bemusement… After all, I no longer have a choice. The price is now determined by the complex interaction of several independent computer programs, most of which don’t actually have a copy to sell.

Read the whole story: How Bots Seized Control of My Pricing Strategy.

Turing stamp issued tomorrow

As part of its Britons of Distinction Stamp Set, one of a series of special stamp sets issued this year to mark the Queen’s Diamond Jubilee, Royal Mail are due to release a stamp commemorating Alan Turing tomorrow. This features the rebuilt Turing Bombe on display to visitors at Bletchley Park.

Bletchley Park are offering for sale a set of first day covers. According to ebay, “first day cover”:

refers to an envelope on which a stamp is pasted and the stamp gets cancelled on the very first day of issue. A cachet is placed on the left side of the envelope that describes the stamp’s issue. The cachet is a design that will explain the event or anniversary being commemorated. The stamps affixed are related to some events. The first day cover stamps are must haves for the first day cover collectors.

The first day covers are produced in association with the Alan Turing Centenary Year Committee and Bletchley Park Post Office, with proceeds from sales going to support Bletchley Park. According to a Bletchley Park press release:

The first design is by Rebecca Peacock of Firecatcher Design and the theme is Turing’s work on the mathematics of patterns.  It was Turing’s genius for mathematics that made his work so vital to Bletchley Park and the development of modern computing.
The other three are original paintings by artist Steve Williams who has donated his work to the Bletchley Park Trust. They depict three buildings at Bletchley Park associated with Alan Turing.  These are the cottage and Hut 8 where he worked and Hut 11 that housed the Turing Bombe machines.
The Royal Mail stamp features the rebuilt Turing Bombe on display to visitors at Bletchley Park.  The first day of issue postmark is a facsimile of one of the Bombe’s 36 drums marked with letters of the alphabet.

Stocks are limited (1000 for the first design; 500 each of the others) so early ordering is recommended.

First Day Covers at Bletchley Park Shop.

Press release: Bletchley Park Puts Stamp On Turing Centenary.

Alex the parrot could count to eight

The Nature News Blog reports on a new addition to the non-human numerism literature:

Even in death, the world’s most accomplished parrot continues to amaze. The final experiments involving Alex – a grey parrot (Psittacus eithacus) trained to count objects – have just been published.

They show that Alex could accurately add together Arabic numerals to a sum of eight and three sets of objects, putting his mathematical abilities on par with (and maybe beyond) those of chimpanzees and other non-human primates. The work was just published in the journal Animal Cognition.

Experimental evidence for Turing’s morphogensis mechanism

Alan Turing’s research in the latter part of his life focused, among other things, on morphogensis – particularly of animal pattern formation.  According to a King’s College London press release, Turing “put forward the idea that regular repeating patterns in biological systems are generated by a pair of morphogens that work together as an ‘activator’ and ‘inhibitor'”. Now researchers at Kings have provided experimental evidence to confirm this theory. This study:

not only demonstrates a mechanism which is likely to be widely relevant in vertebrate development, but also provides confidence that chemicals called morphogens, which control these patterns, can be used in regenerative medicine to differentiate stem cells into tissue.

The press release quotes Dr Jeremy Green from the Department of Craniofacial Development at King’s Dental Institute saying:

“Regularly spaced structures, from vertebrae and hair follicles to the stripes on a tiger or zebrafish, are a fundamental motif in biology. There are several theories about how patterns in nature are formed, but until now there was only circumstantial evidence for Turing’s mechanism. Our study provides the first experimental identification of an activator-inhibitor system at work in the generation of stripes – in this case, in the ridges of the mouth palate.
“Although important in feeling and tasting food, ridges in the mouth are not of great medical significance. However, they have proven extremely valuable here in validating an old theory of the activator-inhibitor model first put forward by Alan Turing in the 50s.
“Not only does this show us how patterns such as stripes are formed, but it provides confidence that these morphogens (chemicals) can be used in future regenerative medicine to regenerate structure and pattern when differentiating stem cells into other tissues.”

Source: Scientists prove Turing’s tiger stripe theory.

Why maths, Dara O’Briain?

Dara O’Briain has written a piece for the Telegraph’s numeracy campaign. Dara, as he explains, has “a deep passion for maths and physics”, having studied mathematical physics at University College, Dublin prior to starting his career in comedy.

Dara writes about maths and “cool”.

I’m often asked to speak about science, in the vain hope that the perceived “cool” of entertainment will somehow rub off onto the science and make it more alluring. Nothing like a heavy, bald 40-year-old to make something “cool”.
Listen. Maths is never going to be “cool”, other than to the sizeable rump of destined-to-love-it-no-matter-how-it’s-presented kids who are like I was at 15.

He argues that maths should be compulsory in schools, like PE, because it is good for pupils, giving both pragmatic – “exercise for the brain” – arguments and philosophical ones. The latter is likely to more attractive here:

Maths is one of the greatest achievements of humanity. It is the common language of science; it has allowed us to drag ourselves from ignorance by creating communal knowledge, which in turn enables us to master our world and to understand our universe. Maths teaches us to spot patterns, to predict behaviour and the steps of an argument. Maths is, above all, a way of approaching problems – stripping things down, extracting the relevant information, and then solving them.

Improving numeracy, Dara says, is more than just enabling people “to be faster at calculating the cost of the weekly shop”, citing the use of statistics in “a world of claim and counterclaim”.

Maths reform campaign: Sum up: you’ll hang on to your knighthood.

Shaping capabilities, but not maths yet

EPSRC has announced the next set of decisions under its controversial “Shaping capabilities” programme. Under this, according to a story in Times Higher Education, the Research Council:

has divided its portfolio into 111 subject areas and is mulling over whether to increase, maintain or reduce funding for each of them according to their research excellence and existing capacity, as well as their national importance.

The first round of decisions provoked controversy last July when “EPSRC decided that it would not accept applications for research fellowships in any area of the mathematical sciences except statistics and applied probability, until further notice”.

Now, according to Times Higher Education, the second set of decisions are confined to energy, ICT and engineering. Most areas will be maintained, but seven will grow. The only reductions are in biological informatics, and in hydrogen and alternative energy.

EPSRC has deferred until the end of March more decisions on which areas of mathematics and physical sciences will grow or shrink.

Times Higher Education: EPSRC rolls out 31 shapes but puts off decisions on the difficult subjects.