Understanding one of the more profound questions in computer science and mathematics pertaining to computational complexity, holds the key to understanding the investment style we adopt. In an era when possibly one of the most successful active fund managers in the history- Warren Buffett- argues for passive/ index investing- it is natural to ponder over the efficient market hypothesis. Are the markets truly efficient? Can a fund manager/ investor not beat the markets? The answer to this question lies in our understanding of one of the seven Millennium Prize Problems set forth by the Clay Institute for Mathematics: P=NP

Understanding P vs. NP

P vs. NP speaks to the computational complexity of problems; i.e. how easy or difficult is it for a computer program to solve the problem. 

‘P’ is a set of problems that can be solved in a fairly short amount of time by a computer program. ‘P’ therefore stands for polynomial time implying that the amount of time taken for a computer to solve the problem under this set, is a polynomial function of its size. N, N-squared, N-cubed, etc. are all valid components of the polynomial function.

Figure 1: A Polynomial Function

‘NP’ on the other hand denotes those problems for which, solution if given, can be checked easily by a computer program. ‘NP’ stands for Non-deterministic Polynomial time implying polynomial time checking but not solving. These problems include functions whose complexity can be modeled by an exponential  function (such as 2 raised to the power N), which increases far more rapidly than polynomial functions as N increases. A classic example of this would be Sudoku- though it is difficult to solve a Sudoku problem as N increases- checking a solution to one is fairly simple. 

Figure 2: An Exponential Function

What the realm of computational science is struggling with right now is to understand if problems in NP can be a part of P, i.e. is P=NP. The fundamental question they are trying to therefore answer is: If a solution to a problem can be checked in polynomial time, can the same solution be found in polynomial time by a computer?

Applying Computational Sciences to the Market

The efficient market hypothesis essentially states that it is impossible to beat the market; for the the stock market efficiently incorporates and reflects all the relevant information. If the market truly analyses and reflects all the relevant information- it must imply that the markets essentially posit a class of problems that can be classified in the ‘P’ category of problems- i.e. they can be solved fairly quickly by an efficient computer and therefore give us a solution in the form of true price of an asset easily. 

Markets at the very fundamental level are resultant of an interaction between supply and demand for a given asset. The supply and demand is however governed by individual participants in the market that have bounded rationality. Bounded rationality is the idea that rationality of individuals during decision making is limited by the information they know, the cognitive boundaries of their minds and the limited amount of time they have to decide.

Therefore the problem of markets can be seen as a computational question with interactions between the various market participants. Solving through the possible permutations of these interactions results in a complexity function that is factorial in nature (given the possible outcomes in a permutation). 

Figure 3: A Factorial Function

As ‘N’ increases, factorials grow faster than all polynomials and exponential functions. This implies that markets certainly do not fall under the ‘P’ category of problems and possibly fall even outside of the ‘NP’ category of problems; i.e. even after a solution is given one cannot answer the question if it (the answer) is truly the best possible ‘solution’ to a given problem.

Figure 4: Graphical Representation of Various Functions

Markets ain’t efficient

Leaving the arithmetic aside, markets conceptually posit a computational monstrosity that grows in size as the number of transactions and number of participants increase. We do not have a program that can arguably model the behavioral biases and eccentricities of millions of individuals executing trades on a daily basis. Even in a static state it presents a number of permutations so high, that it cannot be solved for by a program. And biases are not constant as human nature and limitations are forever evolving.

Buffett’s belief in passive investing or at least a weak or semi-strong form of market efficiency is inconsistent not only with his own wealth creation journey but also with the belief held by my most computer scientists: P in fact does not equal NP. This of course is yet to be proven, and a million dollars from the Clay Institute are yet up for grabs.


Note: This idea and its consequent articulation was provoked by the following video sent by a friend of mine: P vs. NP and the Computational Complexity Zoo. To those interested, the video gives a fundamental understanding of the P vs. NP problem.