You're reading: Phil. Trans. Aperiodic.

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?

Every odd integer larger than 1 is the sum of at most five primes

Terence Tao has uploaded to the arXiv a paper “Every odd number greater than 1 is the sum of at most five primes“, submitted to Mathematics of Computation. He says this result is:

in the spirit of (though significantly weaker than) the even Goldbach conjecture (every even natural number is the sum of at most two primes) and odd Goldbach conjecture (every odd natural number greater than 1 is the sum of at most three primes). It also improves on a result of Ramaré that every even natural number is the sum of at most six primes. This result had previously also been established by Kaniecki under the additional assumption of the Riemann hypothesis, so one can view the main result here as an unconditional version of Kaniecki’s result.

Interesting Esoterica Summation

I feel like it’s time to do another summary of my recent additions to the Interesting Esoterica collection.

A reminder of what it’s all about: every now and then I encounter a paper or a book or an article that grabs my interest but isn’t directly useful for anything. It might be about some niche sub-sub-subtopic I’ve never heard of, or it might talk about something old from a new angle, or it might just have a funny title. I put these things in my Interesting Esoterica collection on Mendeley.

In this post the titles are links to the original sources, and I try to add some interpretation or explanation of why I think each thing is interesting below the abstract.

Click here to continue reading Interesting Esoterica Summation on cp’s mathem-o-blog

Interesting Esoterica Summation

I’m going to try collecting additions to my Interesting Esoterica collection in let’s-say-weekly posts. I’ll link to each item, maybe paste its abstract, and write a sentence or two about it. Let’s see if it catches on. I’m not sure if I’ll have the will to do this regularly. I’m in a bit of a getting-things-done mood today.

As this is the first one, and I’ve added loads of stuff in January, for this first post I’m using everything  I’ve added since the New Year. Future posts shouldn’t be anywhere near as long.

I should explain what the Interesting Esoterica collection is about.

Click here to continue reading Interesting Esoterica Summation on cp’s mathem-o-blog