To celebrate the 50th aniversary of the discovery of NP-complete problems by Stephen Cook, a Symposium was organized by the Fields Institute. Scott Aaronson gave a talk on the the role of physics in solving NP hard problems and it is a fascinating account.

 At the start the topic is what is not the topic - which is sort of appropriate at the logical level. What the talk is about, and I'm telling you in the hope that you won't even have to waste 5 minutes of your time watching the video, is:

"are there any physical means to solve arbitary NP problem in polynomial time."

You could also phrase this as are there analog computers that solve NP problems in polynomial times.

This is a topic dear to my heart ever since I described a way of finding the maximum of a list of numbers in O(1), i.e. constant time - take a pack of spaghetti, cut each piece to the length of one of the numbers of interest and then holding a fist full of the spaghetti tap on end down on the table and pull out the longest piece which will be clearly visible. From then on I was given the appellation of "spaghetti monster". I was also taken to task for not including the time to prepare the spaghetti lengths - look it was just an example!

This video considers similar ideas but at a little more advanced level. It isn't just a pure theoretical question because quantum computers are physical systems that might just solve NP problems in polynomial time. Can they? Is there some law of the universe that means they cannot? Studying physical systems that can, or can seem to, solve NP problems should give us insight into how to go about the quantum case.

So, if you're still interested watch the video:

Does this mean P=NP?

The answer is more that what a physicist thinks an NP-hard problem is is different from what a computer scientist thinks it is. A scientist seems to think that solving a large enough set of examples of problems that are in NP is a physical proof that NP=P. The computer scientist points out that not all examples of NP problems are actually difficult. There are easier problems even in a type provably in NP and unless you can show that your physical class is large enough to include all NP problems of that type you haven't got a result of much significance.

My spaghetti computer, for example, can solve all sorting problems in the same time - but, of course, sorting isn't in NP.

There are many other interesting talks at the symposium and the videos are well worth watching. As Scot Arronson puts it:

check out the other talks as well—they’re by an assortment of random nobodies like Richard Karp, Avi Wigderson, Leslie Valiant, Michael Sipser, Alexander Razborov, Cynthia Dwork, and Jack Edmonds.

More Information

Symposium on 50 Years of Complexity Theory: A Celebration of the Work of Stephen Cook

NP-complete Problems and Physics: A 2019 View

Related Articles

Knuth Prize 2019 Awarded For Contributions To Complexity Theory

Google Takes On Quantum Computing

DARPA Wants Analog To Boost Super Computer Performance

Google Announces 72-Qubit Machine

Proof Of Quantum Supremacy?

Minecraft Goes Quantum       

The Theoretical Minimum       

$100,000 Prize For Proving Quantum Computers Are Impossible

Solve The Riemann Hypothesis With A Quantum Computer       

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info