Collapsing the Polynomial Hierarchy is ‘Dangerous’

by noospheer

Not only is P vs. NP the defining question of our field; it’s one of the deepest questions ever asked for which we’d know how to recognize an answer. (In other words, one of the deepest questions in NP.)

Aaronson, p.1

quantum relic

A rigorous and therefore undeniable mathematical proof demonstrating a collapse of the polynomial hierarchy (PH) has a large number of big implications for the world beyond math and science.

  1. First, in terms of math and science; a successfully collapsed PH is closely related to efficient classical emulation of quantum systems (via post-IQP circuitry); in other words, regular computers may be fully capable of being quantum computers. The mainstream understanding — as alluded to in the post-IQP paper — is the rather naive one that quantum computation requires processors which demonstrate quantum effects as we currently define them. The mainstream is missing the point: computer science is, at its core, linguistics. If we know the math (which we do quite well), and assuming the Church-Turing thesis is actually universal, then we just need to teach our machines how to run the calculations (by writing insanely great code). One is now free to imagine a planet (such as this one) suddenly bustling with quantum computers, which include your laptops, cell phones and satellites. tada! [For the skeptic: W, X, Y, Z, 1, 2, 3 (pIQP demands a linear sample rate for PH collapse) It is also important to note that a collapse of the PH does not necessarily imply P = NP, however the two are inextricably related and are both considered ‘improbable’]
  2. What about our institutions/ourselves — specifically with regard to information privacy? The only factor which maintains a state of separation among entities in a shared space is unshared data. That said, with 1. in mind, the first thing a security guy/gal might consider is a ubiquitous encryption method called RSA being compromised. [Fun Fact: RSA was published 7 years after P v NP was formalized.]  Long story short, if 1. becomes a reality, then the invincible armor shielding governmental, financial, corporate, and an increasing amount of personal data from ‘adversaries’ — suddenly meets Kryptonite.Please consider this another early public WARNING: Any software we write which runs Shor’s factoring algorithm (or any QA) in polynomial time (efficiently) may likely render some encryption methods crackable, and will be published and distributed as a proof under language outlined in the Free Berkeley Software Distribution license.
  3. 2. outlines the atomic tip of the iceberg. Implications for medicine, energy, and time travel abound as well.

Dangerous, or benign? Probably both.

Advertisements