P = NP

Simple and concise. However, the meanings behind it are anything but. The deceptively straightforward equation carries tremendous implications in the contemporary world.

 

***

Computational Narnia

 

The equivalency of P and NP is widely considered the most important outstanding question in theoretical computer science. It has invited many attempted proofs, all to no avail. In its essence, the equation asks: Does P (problems that are easy to solve) equal NP (problems that are hard to solve, but can be easily checked)? In other words, is it computationally possible to generate an answer for all problems that have an easily verifiable solution, regardless of how difficult they seem? The equivalence of P and NP would indicate yes. To a tech geek like myself, that is much like pronouncing the existence of a computational Narnia—a magical land where the unthinkable is possible, albeit with its own dark secrets. For those who aren’t deeply involved in the computing world, the obsession over this question may not seem obvious. However, it is intricately tied to many modern-day functions such as cryptography, cures for terminal diseases, and more. 

 

As Lance Fortnow describes in his book, The Golden Ticket: P, NP and the Search for the Impossible, if P does indeed equal NP, this will be validating “a world of total ease and confidence that there is an efficient way to calculate nearly everything”, including “the nature of the universe” itself. Without diving into excessive technical details, I’d like to entertain the idea of what the world would look like if this is the case— that there is an algorithmic process capable of validifying a problem’s solution, then reverse-engineering a feasible solution. This is undoubtedly an unbelievably expansive topic that warrants a deeper probe into its many subsidiaries—all of which I’d love to speak to. However, the goal of this piece is to act as a high-level (and hopefully intriguing) introduction for those who may not be familiar with this subject. Computational breakthroughs aside, what are the social and ideological implications if P = NP? How might it affect future developments in artificial intelligence (AI) and human-computer relations?

 

***

Imagine for A Second

 

In a world of easily computable bliss, where P = NP, there are immense possibilities as to what we could accomplish. In this world, simply being able to check the solution would suggest that a computer with sufficient computational power and time could generate the solution itself. What P = NP seems to promise is a possible solution to every conceivable human problem there is. We could cure cancer. By examing a cancer patient’s DNA, we identify the mutation within proliferating cancer cells and develop proteins that fold in just the right ways to counteract the mutation without affecting the normal cells. We could solve

global climate change. Using a system that verifies the concentration of greenhouse gas in the atmosphere, it can monitor factors such as CO2 emission and rates of deforestation to calibrate restorative measures. Despite all the optimism, one of the largest concerns of proving P = NP is that it will render the majority of our current cryptographic systems obsolete (including symmetric-key and public-key). Since modern cryptography is based on the Boolean satisfiability problem (SAT), an NP problem, a P-NP equivalence means security codes will no longer uphold its complexity. However, the effects of the proof will not be as severe as perceived considering the establishment of P = NP will not immediately debilitate current systems. It could still be eons before a polynomial-time algorithm is developed for SAT. Even then, the success of that algorithm is dependent on various things such as constant factors and computing memory capabilities. What I’d be concerned with isn’t the breakdown of any of our current computational systems, but more so the unintended social consequences that may come out of this idealistic equation.

 

***

The Power of An Ultimate Answer Key

 

It isn’t surprising that individuals and organizations with malignant agendas often take advantage of technology for unethical or terrorizing acts. Hence the plotline inspirations for all those Marvel movies. As convenient as the discovery of “P = NP” would be, it would inadvertently open up possibilities of its misusage. For instance, a political leader could hire a super-computer and feed it the data of every citizen’s behaviors. This could be anything from people’s daily physical interactions to cyber-footprints which reveal how they think and act. This computer then has the capability to craft a propaganda method that could, theoretically, manipulate any and every individual it engages with based on what they like, dislike, trust, fear and believe. The social platforms today already have the power to influence the outcome of entire elections (looking at you, 2016 U.S. presidential election) with amateur bots and fake accounts. Social algorithms have been taken advantage of to fabricate false truths and spread misconceptions of the social atmosphere. Imagine what a computer could do if it can calculate with computational perfection every citizen’s desires and weaknesses. Confirmation of P = NP would give rise to a new form of indoctrination previously impossible with human coordinators, but now achievable using all-knowing computers. Politics aside, human opinion and thought itself will be highly susceptible to outside influence. What we hold firm and private in our heads are no longer safe as computers conditioned to manipulate human thought can devise ways to penetrate our minds. These vulnerabilities could be exploited in any other industry outside of politics: medicine, law, education, communications, and more.

Society would become conditional and extremely volatile as acknowledged truths and beliefs are no longer consistent. This leads into a deeper discussion of what truth in the modern day is, but in consideration of the length of this piece, I will save that for another discussion. At this juncture, I’d like to transition into a discussion of philosophical implications and applications of “P = NP” in AI.

 

***

A Segue Into AI

 

The proof of P = NP would unquestionably empower many aspired functions of AI because of the computational efficiency it promises. However, even if the proof does not ever complete, the current trajectory of AI developments could eventually take us very close to the state prescribed by P = NP. Contemporary intelligent machines are built with large amounts of experiential data that imitate human capabilities within the AIs. Their self-learning algorithms proceed to self-iterate and improve upon these abilities and eventually surpass human limitations to “maximize” these functions. At that point, intelligent machines would

reach a state of computational efficiency that practically simulates P = NP.

 

***

The Originality Gap

 

Despite the technical nature of the P = NP problem, there are ideological considerations closely related to it. For one, taking a philosophical approach, if P = NP there would be no fundamental gap between checking the feasibility of a solution that’s already been found and devising the solution in the first place. By the same logic, it would only be a matter of time before an algorithmic method is developed that could generate cognition or verifiably “great” artworks. It’s true— AI has produced artwork replicas that even professional art-authenticators can’t distinguish from the original piece. This takes us down a path where

anyone—human or machine, though most likely the latter— who could replicate Starry Night is Van Gogh; anyone who could appreciate Symphony No. 40 is Mozart. The originality gap will cease to exist. So, what’s left of us, the human creators? We’d like to believe that there is an impenetrable gap between the original creation of something and the mere comprehension of it, no? After all, that is the basis on which we preach the distinction between human and machine: humans have the capability to originate thought and actions, not just replicate solutions based on historical data with readily clear answers. We pride ourselves in our ability to navigate ambiguity and open-endedness, as opposed to machines and programs who aren’t so flexible and functions off of requisite instructions. Yet, if we achieve the computational efficiency and totality that P = NP implies, there will be no such distinction, at least theoretically. When that happens, what will the next great leap in the human frontier be? Or will we hand the reins to our robo-counterparts thereafter?

 

***

Final Thoughts

 

It seems that to postulate P = NP, we are doing away a world of mystery and difficulty but at the same time, we are losing the gratification of inquiry and discovery. Though the jury isn’t out on this complex problem of whether P = NP just yet, a future simulating its possibilities is quite probable. It certainly is worth our attention to consider the implications of what it could mean to our notion of creative originality and the relationship between humans and intelligent computers in the future.