2
$\begingroup$

The title sort of says it all. We discovered through some ingenious use of obscure mathematics a way to solve any NP-Complete problem with an algorithm that completes in a Big-O of n*log(n) time.

What significant changes would occur over the next year as individuals start to implement this algorithm to solve previously believed to be effectively unsolvable, due to the cost of computing the answers.

One of the most obvious to me is that most (all?) public/private encryption schemes will fall apart, which will render most encryption on the internet invalid. I'm sure hackers and the like will love that. However, I'm sure there are a number of other major areas that will be affected by the discovery.

$\endgroup$
  • 4
    $\begingroup$ All economies crash as cryptography ceases being a thing. $\endgroup$ – Renan Nov 4 '19 at 17:02
  • 3
    $\begingroup$ "What is effect of X on the world/society?" Is the stereotypical too broad question. $\endgroup$ – L.Dutch - Reinstate Monica Nov 4 '19 at 17:03
  • 1
    $\begingroup$ All cyphers fall apart, both symmetrical and public-key based; all digital signatures become completely unreliable (which will induce quite a bit of economic fallout). Computing the shape of a protein becomes trivial. Lots and lots of optimisation problems (for example, in transport networks) become suddenly easy. Etc. $\endgroup$ – AlexP Nov 4 '19 at 17:04
  • 1
    $\begingroup$ @AlexP breaking a symmetric cypher is not an NP-complete problem. $\endgroup$ – Starfish Prime Nov 4 '19 at 18:02
  • 1
    $\begingroup$ @StarfishPrime: No, it's not NP complete, but it is trivially easy to do with a nondeterministic algorithm. (There is a difference between NP complete problems, and problems which admit a nondeterministic algorithm running in polynomial time. An NP complete problem is a problem which admits a polynomial-time nondeterministic algorithm, and in addition solving it with a deterministic algorithm running in polynomial time would generate an immediate solution to all NP problems.) $\endgroup$ – AlexP Nov 4 '19 at 19:29
2
$\begingroup$

Regardless of whether the new algorithm is practical, the mathematician collects $1,000,000 from the Clay Mathematics Institute for solving one of their Millennium Problems.

Any consequences beyond that, including but not limited to effect on encryption, depends on whether the solution is practical. An algorithm could take a minimum of a million years to solve any problem and yet be O(n log(n)) time.

If the algorithm is reasonably fast for practical problem sizes, it would have mainly beneficial effects other than the impact on encryption. There are several problems that need to be solved, and are currently handled by "good enough" approximations that could be solved exactly using the new algorithm.

Airlines are continually solving massive integer programming problems to schedule aircraft and crews. They need to change the solution any time a crew member is unexpectedly unavailable or an aircraft has a maintenance problem. Quick exact solutions might reduce delays and save money by making optimum use of aircraft and minimizing the time and seats crews spend flying as passengers to get to their next flight.

Delivery companies approximate a solution to Traveling Salesman every time they decide on routes for their trucks.

More generally, there are many resource allocation and scheduling decisions that have to be made, where finding the true optimum solution is NP-Complete so we live with approximate solutions that may waste resources.

$\endgroup$
2
$\begingroup$

Contrary to popular belief, not all encryption becomes completely useless. It just gets a whole lot harder. How big of a deal this is depends on the constant factors associated with the algorithmic reduction.

Reliable encryption depends on having a trapdoor function which is unfeasible to break in a "reasonable" amount of time. Choosing a trapdoor function whose compromise constitutes a problem in NP is an easy way to do that right now... but there's nothing inherent about problems that are not deterministically polynomial that makes them the only choice for things that take a long time. Pick a trapdoor function where, sure, it can be broken in n*log(n) time, but the constant factors make it take ten billion times longer than normal decryption anyway, and you've still got something useful.

Additionally, NP isn't the worst complexity class, by far. Which means that even if we can solve non-deterministic polynomial problems in deterministic polynomial time, cryptographers will just start looking for new non-polynomial trapdoor functions that can only be broken in, say, EXPTIME, or EXPSPACE. Since NP decryption is now potentially feasible, there's a much larger space of approaches to play with now.

So: present day encryption probably becomes insecure right away, and there will be an adjustment period while research continues into new approaches, but eventually we'll recover from that.

Aside from that, though, the world rapidly becomes a much better place, due to improved economic efficiencies. All sorts of optimization problems that were previously infeasible suddenly become trivial--at least, above a certain scale determined by the constant factors in the translated algorithms. That means pretty much every large business can save money, and consume fewer physical resources for the same results. Research in theoretical physics, chemistry, and biology also speeds up, as tons of things that were before infeasible to simulate become feasible to simulate exactly. That means less time and money spent on the first wave of lab experiments--we can weed out poor lines of research earlier, and find better lines of research easier, before moving on to confirming things in the real world. At the very lowest levels, we start getting more useful direct results out of lattice QCD simulations that help pin down some of the free parameters in the standard model; at the higher levels, we can have computers design specialized drugs by assembling atoms into bioactive compounds from first principles.

$\endgroup$
  • 1
    $\begingroup$ (1) NP means non-deterministic polynomial, not non-polynomial. (2) All encryption becomes useless if NP problems can be solved in $n \log n$ time. After all, there is a trivial algorithm to brute force the encryption key on a non-deterministic computer: just try all the key bits as zero and one in parallel. Hey presto, cipher broken in $O(n)$ time. (3) All trapdoor functions are trivially easy to brute force on a non-deterministic computer, for the same reason. $\endgroup$ – AlexP Nov 4 '19 at 19:34
  • 1
    $\begingroup$ I agree with @AlexP. There are two, equivalent, ways of defining NP. One is the set of problems that can be solved in polynomial time by a non-deterministic TM. The other, which I find more intuitively useful, is the set of problems for which there is a polynomial time solution checker. If you can check for successful decryption in polynomial time, decryption is in NP. $\endgroup$ – Patricia Shanahan Nov 4 '19 at 20:12
  • 1
    $\begingroup$ @AlexP Brute-forcing the encryption key does not work for arbitrary encryption algorithms. E.g., it doesn't work for one-time pads. Brute-forcing the key only works when you know that the key or the ciphertext have some mathematical structure than can be independently verified. Thus, if you have a non-deterministic polynomial computer, you have not changed the fact that it is still limited to problems which are polynomial under non-determinism, and an encryption system whose keys require an EXPTIME, or NEXPTIME, or EXPSPACE algorithm to brute-force will still be safe. $\endgroup$ – Logan R. Kearsley Nov 4 '19 at 22:25
  • $\begingroup$ @AlexP I am aware of NP means, but on re-reading I can see that my wording is easily misinterpreted. I have edited to try to make my point clearer--you can choose a polynomial trapdoor function with a huge constant, or you can choose a function that is not deterministically polynomial, and either one is a valid route to a useful cryptosystem. $\endgroup$ – Logan R. Kearsley Nov 4 '19 at 22:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.