I think a lot about P vs NP. I think it’s the most interesting problem ever, and my opinion on the subject is pretty well known. Here’s my latest thought.
Computation is all about state changes; every computer ever built is a finite state machine of some kind. For those unversed in Computer Science terminology, a finite state machine is an abstraction with a finite number of discrete states. It starts out in a specific state, and when it receives input from an alphabet of discrete symbols, it changes from one state to another. For example, a toggling light switch has two states: on and off. When you push the button, the toggle moves to ‘off’ if it was in the ‘on’ state, and it moves to the ‘on’ state if it was in the ‘off’ state. More complex machines have more states, and more complicated rules for transitioning from state to state.
As I was saying, every computing device ever built is a finite state machine. Fingers change state from extended to contracted. An abacus changes state when its beads are moved. The Antikythera mechanism and Difference Engine changed state by movement of gears. Modern electronic computers change state by modifying electronic signals. People have proposed optical computers which operate based upon switching light sources on and off. Note that these state changes are all discrete – gears could be said to move continuously, but they have an integer number of teeth, and therefore an integer number of possible discrete states. Electricity is the flow of electrons, and light consists of discrete photons. Fingers are, well, fingers.
What about analog computers? Fans of slide rules might argue that they involve an infinite number of states as a result of their continuous nature. Here I will make a conjecture: just as Planck proved that energy occurs in discrete chunks, we will also come to find that time and space are discrete. That slide rule may appear to move continuously, but I’m willing to bet that it’s actually moving in discrete jumps which are so tiny we cannot measure them. I am not alone in putting faith in this conjecture.
If computation involves state changes, a logical question is, “For a given problem, how many state changes are necessary to solve it?” If a problem requires at least ten state changes to solve, and time is composed of discrete units, then there is a lower bound on how quickly that problem could be solved. I realize there are a lot of basic questions that would have to be answered for this theory to prove useful, but my guess is that we will eventually discover that the “minimum number of states” problem is akin to the problem of finding the Kolmogorov complexity of a string; that is to say, it is impossible to devise a general purpose algorithm that always gives the correct answer. (In fact, I think I’m going to try to prove this result myself.)
What does all of this mean for P vs NP? Even if the ‘minimum number of states’ problem is not solvable by a general purpose algorithm, perhaps someone can construct a proof of the minimum number of state changes for a particular problem. If someone could do that for an NP-Complete problem, then they could finally determine the answer to P vs NP. I’m accepting bets that P = NP. Any takers?