We often hear that what’s hard for humans is easy for computers. But it turns out that many kinds of problems are exceedingly hard for computers to solve. This class of problems, known as NP-Complete (NPC), was independently discovered by Stephen Cook and Leonid Levin.
A possible solution for an NPC problem can be checked for correctness very quickly, but finding a good solution takes a very long time. That is because the length of time required to find a solution grows exponentially with the size of the problem, at least as far as we know. For example, with 266 binary variables, solving the problem will require checking more solutions than there are particles in the universe.
This problem points the way toward a scientific test for intelligence that will give us insight into its nature. For example, supppose we identify problems that humans can routinely solve easily but are in the NPC class for computers. We can then pick a problem size that will be impossible for a computer to solve in the lifetime of the universe, even with a universe’s worth of computational power. If at the same time a human can still solve the problem, there are a few possible conclusions we can draw:
- Something special about the particular problem makes it easy for a computer to solve. While, in general, NPC problems are hard for computers to solve, certain sub groups happen to be easy. We want to avoid confusing the issue by accidentally picking a problem in that subgroup for the human to solve.
- The human mind can access the special algorithm that can solve NPC problems.
- The human mind operates on a non-physical plane.
To eliminate #1, we randomly pick our problem and run many, many tests. This achieves the level of scientific certainty.
Eliminating #2 is more tricky. But narrowing the scientific possibilities of explaining the human mind down to #2 and #3 is in itself a major achievement.
Alternatively, if we are unable to find any NPC problems that humans solve easily, then we can safely conclude the human mind is probably reducible to a computer program.
It turns out that many tasks and games — including games that humans routinely solve for fun — are NPC problems. Even though these games include Chess and Go, both of which feature computer grand masters, when we look in detail at the computer players on an equal playing field, they are vastly inferior to human players. That leaves open the possibility that a modest increase in the size of the game board and the number of pieces might enable us to create versions of Chess and Go in which humans will always beat computers.
Next: A Scientific Test for True Intelligence
Previous: Current artificial intelligence research is unscientific. The assumption that the human mind can be reduced to a computer program has never really been tested. Because AI research is based on a fundamental assumption that has not been scientifically tested — that the human mind can be reduced to a computer — then the research itself cannot be said to be scientific.
See also: Math shows why the mind can’t be reduced to a formula. The Liar’s Paradox shows that even mathematics cannot be reduced to a fixed set of axioms. Gödel’s discovery brought back a sense of wonder to mathematics and to the rest of human knowledge. His incompleteness theorem underlies the fact that human investigation can never exhaust all that can be known. Every discovery builds a path to a new discovery.