Scott Aaronson On NP And Physics
Written by Mike James
Tuesday, 11 June 2019

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

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.

 Google AMP Joins OpenJS Foundation18/10/2019Google has announced its AMP framework will join the OpenJS Foundation. AMP has been open source for the last four years, but the move will make it less Google-centric. + Full Story Developer's Facility Used To Create Open Apple App Store30/09/2019AltStore - cute name - is an alternative to the App store that you can use to install programs that are not under the control of Apple - and all without jailbreaking your phone. How can the walled gar [ ... ] + Full Story More News

#### Comments

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

Last Updated ( Tuesday, 11 June 2019 )