Computational Complexity as a Law of Nature

I have to admit I know nothing about this topic, however, it is, as far as I can say, one of the weirdest and most interesting recent developments in physics. It is also closely linked to computer science. Yet, I don't see it discussed in programming community at all.

The idea is that, somehow, nature may be fundamentally limited in its computational capacity. That, in other words, it's not possible to compute NP-complete problems in polynomial time and that the hurdle is not some kind of technical problem but rather that uncomputability of such problems is a fundamental principle of physics.

Sounds like a hallucination by a computer science professor? Well, given that an accomplished physicist, such as Leonard Susskind is willing to take it seriously maybe it is not.

And, by the way, if I had to choose between a universe with limited computational power and a universe with limited amount of certainty, the former sounds much less wacky.

In any case, watch the video and wonder: https://www.youtube.com/watch?v=boZyu6NhAcI

Martin Sústrik, December 7th, 2017

Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License