The equation that would change the Internet and solve the world

By LANCE FORTNOW

Dateline: April 15, 2023, Server 3827.4A8

Five years after the anniversary of the Great Discovery of the Algorithm, I’ve been asked to write this short piece looking back on the incredible, revolutionary effects of P = NP on the Internet. Which is a piece of cake, given that I’m a simple computer program capable of producing this article mere seconds after the editor asked me to write it. I can even have this article instantly translated perfectly in 127 different languages. These days I’m proud to say I actually produce all the articles on the Daily Dot; algorithms like me generate nearly every written document on the Web longer than a tweet. Remember when humans had to write the stuff they read? And only in one language? What a waste.

To get a sense of how profound the P = NP solution was, let’s go back to the world before 2018. Computer technology kept getting faster, and algorithms kept getting smarter. But some problems still seemed just too difficult to crack. For example, back in 2016, the NSA intercepted some chatter about a terrorist group RXKY about to deploy a major attack. They knew the code names of the members and the connections between them but they didn’t know the real people behind the names. With a court order they went to Facebook to find the pattern of connections in Facebook’s social network.  Facebook put their best engineers on the problem and still failed to find the pattern, just too many possibilities to search. Luckily, the government still found the members of RXKY—based on a careless phone call by one of them which let them anchor the pattern—or we might have seen a real disaster.

And then there was a failed attempt to optimize the evacuation of Fort Lauderdale, before Hurricane Marie leading to mass hysteria and could have led to thousand of deaths had Marie been as strong as predicted. And, of course, you all remember the great 2015 week-long black out of the entire Eastern seaboard, caused by a coincidence of small glitches that, had we known to look for, we could easily have stopped.

The reason why humans still couldn’t solve these complex problems despite huge advances in technology had to do with a mathematical puzzle known as the P versus NP problem. NP refers to problems where computers can check an answer quickly. Once the government knew the list of terrorists, for example, Facebook could easily check that these terrorists fit the pattern the government was looking for. P is the set of problems we can solve efficiently. If P = NP, then if we check a pattern, we can find it. If P = NP, the RXKY terrorists would have been found in seconds. 

Back then most computer scientists believed that P and NP were different, that there was no possible algorithm to solve the terrorist search problem quickly. There was even a million dollar bounty on a proof that P and NP were different, courtesy of the Clay Mathematics Institute.

That all made what happened on this day in 2018 so amazing. Researchers in South Korea discovered what we now call “The Algorithm,” a method to solve all the NP problems which showed that indeed P = NP. Now we know all too well how The Algorithm is helping us cure cancer, created the perfect tasting low-fat hot dog, and is the key to the design of that ugly-but-aerodynamically-perfect space plane. But since I belong to the Daily Dot, let’s focus on how The Algorithm changed the Internet.

The loss of  “modern cryptography” was the first obvious change. Before 2018 you could securely connect to social networks and e-commerce sites securely just by going to their Web pages. Now one can easily use The Algorithm to invert the encryptions, immediately making everything you send insecure. As a result, for true security we have to go to a store to buy one of those iSecurity devices for each website we use.

But it wasn’t all bad, at all. The Internet became smarter—much smarter, due to an idea known as Occam’s Razor. In the 14th century, William of Ockham developed his principle that the simplest explanation of the data should be considered the best one. This principle, known as Occam’s Razor (since it shaves off the unnecessary complications of a theory), would for the most part drive how scientists model the universe. The hard part was finding that most simple theory that fit the data. The Algorithm changed all that. Now it’s virtually immediate.

Throughout the Internet there were considerable web pages which were hand translations by experts of other documents and web pages. Before 2018, Google Translate used simple statistical information to generate translations of new material but these translations did not seem natural. The Algorithm discovered much deeper connections paradoxically by finding the simplest code that converted, say, French into English. This led to essentially the perfect translation of everything on the Internet. 

And the P = NP Algorithm didn’t stop at translation. Search engines got much better. People would soon come to call them “answer engines,” for they could answer practically any question thrown at them. Ask, for example, “How many hits did Babe Ruth get in the first three games of the 1927 world series?” and the computer would parse the question, find the appropriate box scores and cummulate the results. Far more complex questions couldn’t defeat The Algorithm. Someone ran an experiment and The Algorithm solved every online edition of the New York Times crosswords, in one case finding different—though arguably better—answers from what the puzzle designer had intended.

Again, however, answer engines led to a big loss in privacy. You could learn basically everything about someone based on a picture, a name or even a vague query like “Tell me about that Asian girl I met at Starbucks yesterday.” Today in 2023, most people have decided to just give up any notion of privacy. There is a growing neo-Luddite movement of those who refuse to use the Internet in a mistaken belief that this might actually protect the information they have, not realizing that The Algorithm can determine their secrets from the simplest behavior. One detective uncovered an affair using The Algorithm just by the way the man walked down the street.

The Algorithm, unsurprisingly, also dramatically impacted global economics. Some savvy online traders started used the algorithms to find connections to bet on financial markets. But that didn’t last long, as The Algorithm immediately led to everyone finding any arbitrage and other opportunities leading to efficient pricing of market securities. When everyone has the power then no one does: Hedge funds found out they could no longer beat the market, and stopped trying. A similar event happened on online poker site where players used The Algorithm to optimize their bets—leading to poker reaching an equilibrium, and making the game entirely a matter of chance with no strategy involved.

In the workplace, we started to see huge productivity gains. Nowadays, when you reply to an email, The Algorithm fills out a sample reply for you, finding the information needed in your other emails and on your computer and writing the reply in your own style. More often than not this was entirely sufficient. People didn’t need to even edit the sample reply—they could clear through emails in seconds. People on vacation just had the computer send the replies automatically. Nobody noticed they were even on vacation and some people just stopped working. Of course companies discovered this trend and realized they needed fewer workers.

Computers could write more than just replies to emails. Lazy bloggers and journalists started to use The Algorithm to generate stories. Soon those stories got better than the original authors could have done themselves. And that how yours truly, an algorithm based on The Algorithm, came to be writing this story. The Daily Dot is currently run by two editors and it’s becoming less clear that it needs either one of them.

This is not a Skynet moment. I and my fellow algorithms don’t have a soul or a conscience, and we are not out to take over the world. I am just copying the writing style of humans before me. But you have to ask yourself, if everything you can do we can do better, what is your purpose?

Lance Fortnow is professor and chair of the School of Computer Science in the College of Computing at the Georgia Institute of Technology. He co-authors the Computational Complexity blog and recently published The Golden Ticket: P, NP, and the Search for the Impossible. 

Photo by Bigstock.com