You're reading: Posts Tagged: NP complexity

Math/Maths 89: Remark on a Theorem of Hilbert

A new episode of the Math/Maths Podcast has been released.

A conversation about mathematics between the UK and USA from Pulse-Project.org. This week Samuel and Peter spoke about: Pi day; US judge rules that you can’t copyright pi; Drug Data Reveals Sneaky Side Effect; Researchers Send “Wireless” Message Using Elusive Particles; Computing Power Speeds Safer CT Scans; Mathematics Matters UK Parliament meeting; Mario is NP-hard; ERC rejects ‘impact agenda’; Article Titles Make a Difference; Half of children find science and maths too difficult or too boring; Careers advice cuts could be putting kids off science; and more.

Get this episode: Math/Maths 89: Remark on a Theorem of Hilbert

Aperiodical Round Up – follow Brits and draw Rubik’s cube cartoon, says the most useless law in the solar system

Hello. It’s been a while since the last Aperiodical. That’s exactly how long it takes me to prepare and write each issue, so here we are.

“Here” is not where it used to be, so I should explain — The Aperiodical is now the name of a big maths conblogerate, of which these untimely collections of miscellanea occupy a small corner. The first four editions of the Internet Maths Aperiodical are still available on ACMEScience.com, and will be for as long as Samuel wants them there.

So, on with the interesting maths links and so on!

Math/Maths 87: Faulty Cables, Ridiculous Buses & Intergalactic Steroids

A new episode of the Math/Maths Podcast has been released.

A conversation about mathematics between the UK and USA from Pulse-Project.org. This week Samuel and Peter spoke about: Samuel’s ridiculous bus trip; Computer programmes with IQ 150; IBM’s Watson and data analytics; Extracting Dynamical Equations from Experimental Data is NP-Hard; OPERA faster-than-light neutrinos experiment UPDATE 23 February 2012; ‘Invisibility’ cloak could protect buildings from earthquakes; How Bots Seized Control of Carlos Bueno’s Pricing Strategy; Calculus: The Musical!; Who says ‘maths curriculum failing to meet the needs of the 21st century’?; Turing Stamp; & more, and Peter spoke to some of the team behind Maths in the City on the occasion of their inaugural London walking tour. Oh, and Samuel forgot to mention Science Sparring Society’s second fight, but the link is in the show notes anyway.

Get this episode: Math/Maths 87: Faulty Cables, Ridiculous Buses & Intergalactic Steroids

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?

Google+