You're reading: Posts Tagged: NP complexity

P might not be NP, reckons Norbert Blum

Norbert Blum of Universität Bonn has uploaded to the arXiv a preprint of a paper claiming to resolve the problem of whether $\mathrm{P} = \mathrm{NP}$, in the negative.

“Proofs” one way or the other turn up on the arXiv pretty much every day, but this one might actually be correct. At least, it’s not immediately obvious it isn’t.

Here’s the abstract:

Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev’s function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies $\mathrm{P} \neq \mathrm{NP}$.

John Baez has very quickly put together a post explaining the very basics of Blum’s argument.  Even more briefly, Blum claims to have shown that the best-case complexity of a function solving the clique decision problem is exponential, not polynomial.

Colin Wright reckons that the proof passes all of Scott Aaronson’s immediate ‘sniff tests’ for a claimed proof of a big problem, and his supplementary list for proofs to do with P versus NP. Those help you spot charlatans and Walter Mitty types, rather than looking at the actual mathematical content.

Obviously, none of us are qualified to even offer a hot take on this, so we’ll all have to wait until more experienced sorts have had a good look.

So, watch this space.

(Personally, my money is on this not quite working, purely based on my natural pessimism)

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 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, 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 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?