Why no one is exponentially smarter than others

By Trishank Karthik Kuppusamy and Ashlesh Sharma

One common counterargument to why universality trumps IQ (which was often misunderstood and misinterpreted) is that “some people are exponentially smarter than others.” Right off the bat, it is not even clear what this statement is supposed to mean. We suspect that it is deliberately vague. In any case, it has one of two meanings, the former of which is more popular, but the latter of which is much more likely.

The first meaning is that some people can somehow do exponentially more work than others. Is it possible? Yes. Is it plausible? Let’s look at this through the lens of computation. One of our working hypotheses is that everything in Nature — including human thinking — can be viewed as computations. Figure 1 illustrates the difference between two people who do significantly different amounts of work in the same amount of time.

Figure 1: The difference between deterministic versus nondeterministic computers. Deterministic computers can take one action at a time given some input, with no access to randomness, whereas nondeterministic computers can take different actions all at once.

To restate the first meaning, the claim is that “muggles” do m^k or polynomial amount of work in m time steps, whereas “geniuses” do c^m or exponential amount of work in the same amount of time (where k is any positive integer, and c is a constant greater than or equal to 2). Some readers would have noticed that there is a connection to the million-dollar P vs NP problem, which is as follows.

(Note that we are now switching between how much work gets done in m time steps, where more is better, and how much time it takes to solve a problem of size n, where less is better.)

Decision problems — which have yes-or-no answers — can be divided into at least two classes. P is the class of problems where a problem of size n takes O(n^k) or polynomial time to solve — where the Big-O notation roughly means “no more than” — on a deterministic computer as in Figure 1(a). NP is the class of problems where a problem of the same size takes polynomial time to solve on a nondeterministic computer as in Figure 1(b), and polynomial time to verify on a deterministic computer. An example of a problem in NP is to see whether a very large number x has a prime factor p where the last digit is 3. By the fundamental theorem of arithmetic and the primality test, it takes polynomial time to verify whether alleged factors meet these conditions.

The open problem of this century is whether P=NP: that is, whether it is possible to not only verify but also solve any problem in NP in polynomial time on a deterministic computer, which is the only type of computer we know how to build right now. This matters because many everyday, simple-sounding problems fall into NP, such as whether a traveling salesman can visit n cities in a budget of less than b dollars. Many computer scientists believe that P≠NP, which means that these simple-sounding problems cannot generally be solved in polynomial time on deterministic computers, because (1) there is a superpolynomial number of possibilities to check in the search space even if we simply decided to simply check them all, and (2) there is no hidden structure to the problem that would let us short-cut this brute-force search. One way to do the former is to use a nondeterministic machine (can you see why?), but we don’t know how to build, using the known laws of physics, nondeterministic machines that scale beyond small values of n. No, quantum computers are not such magical machines.

To restate the first meaning of the original thesis one more time, the claim is that the difference between muggles and geniuses is like the difference between deterministic and nondeterministic machines. We argue that this is very unlikely to be the case, notwithstanding the computational irreducibility or logical depth of ideas. There are two unlikely ways that this can be the case. The first way is that there is a hidden structure to problems in NP that only geniuses are presently, implicitly aware of, rendering P=NP. Thus, it appears as if they do a superpolynomial amount of work for the same kind of “hard” problems. (Presumably these “hard” problems are in NP, so that muggles at least have a shot to quickly verify the work of geniuses.) The second way is that it is possible after all to build nondeterministic machines of the sort that geniuses presumably have in their brains (assuming brains are like complex machines). Either way, geniuses are not really geniuses after all. Either way is good news, because muggles and geniuses can be equalized, and bad news, because a lot of cryptography will be definitively broken, mathematics can be trivially automated (finding a proof would be as easy as verifying it), and other doomsday scenarios will lead to the Kali Yuga.

Figure 2: The difference between various polynomial and exponential time algorithms, plotted using WolframAlpha.

Some might object at this point and say, “Even if the difference in the amounts of computation between muggles and geniuses is not exponential, it may still be a significant polynomial difference in practice.” What does this mean? As illustrated in Figure 2, in practice, O(n) and O(n log n) algorithms are considered efficient, whereas O(n²) and O(n³) algorithms are not. So, what if geniuses are more like the former, and muggles more like the latter? This is certainly more plausible than that geniuses are like nondeterministic machines. However, we don’t believe that this is the nail in the coffin that many suppose it is. Another objection is that geniuses implicitly use better heuristics and approximation algorithms to work around intractable problems. In order to tightly focus this essay, and prevent even more misunderstanding and misinterpretation of a complicated subject, we will address these objections in separate essays.

We believe the second meaning of the original thesis is much more likely and vastly more important: that returns on ideas are fat-tailed. Consider two PhD students of roughly the same intelligence: that is to say, when they were both admitted to the program, it is hard to predict who will win, say, the Turing prize.

Now, even if they independently worked on the same problem, one of them will get to a working answer first, through a combination of happenstance, work, or talent, leading to the winner-takes-all effect. Survivorship bias then filters from history textbooks those were just as capable, but who were just a bit too late.

Table 1: A simple way to classify problems “muggles” and “geniuses” work on.

Even if the students work on different problems, Table 1 suggests how risks and returns on problems are far from being uniformly distributed. It is probably safe to say that most problems are simply not very risky and terribly rewarding, and so many geniuses go unnoticed. Otherwise, we would have many more geniuses than we see now, and we would not give so many of them the title, would we?

All of these effects combined will make the winning student appear “exponentially” smarter than the other without actually being the case. This second meaning is much more plausible, but much less exciting, and therefore much less popular.