AI and The NP Conjecture

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

Wikipedia

Here, counter to popular opinion, I conjecture that P = NP based on considerations from artificial intelligence and economic theory.

Essentially, my claim is that to an artificial superintelligence (ASI) the task of solving any arbitrary problem will converge in difficulty and resource allocation to the task of verifying the solution.

This may seem quite counter intuitive. Most mathematicians and computer scientists believe that P does not equal NP. This is due to the seemingly disparate complexity between verifying a solution and actually implementing it. Nevertheless, given that no one has yet been able to prove that P does not equal NP, perhaps it is time for new theoretical approaches.

To a superintelligence, the most complex computer programs are probably other superintelligences. Virtually any program written to date would be trivial to execute and create for an ASI.

But that brings up many interesting issues. Perhaps we can break programs up by their complexity relative to an ASI. Since most programs that are even apparently complex by today’s standards would likely be trivial to an ASI, the interesting question from the perspective of P=NP is does this scale to other superintelligent programs.

Another important component of this conjecture is related to technological determinism, or the view that given enough time all physically possible technologies will be discovered. An ASI would rapidly accelerate the path to technological determinism. While this is just a conjecture, I claim that the end state of technological determinism is P=NP.

Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger.

However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger. So, Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable). Thousands of other problems seem similar, in that they are fast to check but slow to solve. Researchers have shown that many of the problems in NP have the extra property that a fast solution to any one of them could be used to build a quick solution to any other problem in NP, a property called NP-completeness.

Decades of searching have not yielded a fast solution to any of these problems, so most scientists suspect that none of these problems can be solved quickly. This, however, has never been proven.

Wikipedia

To conclude, AI and The NP Conjecture states that P=NP because to an ASI all easily verifiable problems can also be easily solved. Only time will tell if this conjecture is true.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store