Complexity ...

Reality is quantum, probability driven, where there is no certitude, which means ... one cannot predict the future. With this in mind, channeling Alan Turing comes to mind regarding how complexity has just taken a big step to make practical quantum computing a reality.

MIP* = RE is not a typo. It is a groundbreaking discovery and the catchy title of a recent paper in the field of quantum complexity theory. Complexity theory is a zoo of “complexity classes” – collections of computational problems – of which MIP* and RE are but two.

In 1936, Alan Turing showed that the Halting Problem – algorithmically deciding whether a computer program halts or loops forever – cannot be solved. Modern computer science was born. Its success made the impression that soon all practical problems would yield to the tremendous power of the computer.

But this is not so as long as the computer in question is serial ...

The class P consists of problems which a known algorithm can solve quickly (technically, in polynomial time). For instance, multiplying two numbers belongs to P since long multiplication is an efficient algorithm to solve the problem. The problem of finding the prime factors of a number is not known to be in P; the problem can certainly be solved by a computer but no known algorithm can do so efficiently. A related problem, deciding if a given number is a prime, was in similar limbo until 2004 when an efficient algorithm showed that this problem is in P.

Another complexity class is NP. Imagine a maze. “Is there a way out of this maze?” is a yes/no question. If the answer is yes, then there is a simple way to convince us: simply give us the directions, we’ll follow them, and we’ll find the exit. If the answer is no, however, we’d have to traverse the entire maze without ever finding a way out to be convinced.

Such yes/no problems for which, if the answer is yes, we can efficiently demonstrate that, belong to NP. Any solution to a problem serves to convince us of the answer, and so P is contained in NP. Surprisingly, a million dollar question is whether P=NP. Nobody knows.

Reality ... is digital with analog overide - Robert E.