You have an easy job. Every hour your manager comes into your office and gives you a positive integer. Your job is simply to determine whether it’s divisible by 4.
You’d like to have a single method that decides whether any positive integer is divisible by 4. Because you’re brimming with ingenuity, you build a machine that will solve every instance of the problem for you.
The machine consists of a finite state control, a read-write head, and an infinitely long tape composed of infinitely many tape squares. Each square contains a symbol, which may be a blank.
At each step in the machine’s operation, the read-write head reads the square underneath it. According to the symbol that the head reads and the state that the finite state control is in, the machine performs a set of actions:
-The head may erase the symbol that is on the square and write a new one
-The head may move one square to the left or right
-The finite state control may change its state
If the machine enters a yes-state or a no-state, then it halts.
This machine is very generic, and it can perform a lot of different operations. To make your machine decide whether a given positive integer is divisible by 4, you specify a particular table of behavior that defines its manner of operation.
You happen to know that a positive integer is divisible by 4 if the last two digits of its binary representation are 0. So, for example, your manager comes in and tells you to determine whether 20 is divisible by 4. You know that the binary representation of 20 is 10100. So, you write “1” on square 1, “0” on square 2, “1” on square 3, “0” on square 4, and “0” on square 5. You leave the rest of the squares blank.
So, the machine is going to examine the last two digits in the binary representation. But how does it “know” when the symbol it’s reading is a final digit in the binary representation? Because the rest of the squares are blank, the string of input symbols is followed by blank symbols. So, all the machine has to do is move right until it reaches a blank symbol. Then it moves left one square, and it’s at the final digit in the binary representation.
If that symbol is a “1”, then the machine enters a no-state and halts. If that symbol is a “0”, then the machine moves one square to the left. If the next symbol is a “1”, then the machine enters a no-state and halts. If the symbol is a “0”, then the machine enters a yes-state and halts.
If the machine enters a yes-state, then the positive integer is divisible by 4. If the machine enters a no-state, then the positive integer is not divisible by 4. So, in this way the machine decides whether the positive integer is divisible by 4.
In the case of our example, the answer to the question “Is the positive integer divisible by 4?” is “Yes”. For this instance of the problem, the machine will enter a yes-state, because 20 is divisible by 4.
Because “10100” has five digits, the machine performs five steps before it gets to a blank symbol. Then it performs another step when it reads the blank symbol, changes state, and moves one square to the left. If the symbol written on that square is a “1”, it halts, but if the symbol is a “0”, then it must move one square to the left. Then it reads that symbol and enters a yes-state or a no-state. In general, the machine performs at most n + 3 steps, where n is the number of bits composing the positive integer’s binary representation. n + 3 is a polynomial expression.
We define the time it takes for the machine to carry out its computation to be the number of steps that occur during the computation. So, because the number of steps grows according to a polynomial expression, we say that the machine solves the problem in polynomial time.
A problem that can be solved in polynomial time on a machine like the one that you built belongs to a class of problems called P. Such problems have fast solutions. Problems that belong to P are tractable.
Now, your manager is very impressed with you and your ability to build impossible machines that can’t actually exist, so he gives you a new problem. Now every hour he comes in and gives you a list of cities, the distances between them, and a number. Your job is to decide whether you can visit every city exactly once, without traveling a distance greater than the given number.
You quickly find that it takes a lot more time to solve instances of this new problem than it does to solve instances of the first problem. However, if someone were to guess a solution, it would only take you polynomial time to verify whether their guess was correct. All you would have to do is (1) check whether their route visited every city in the list, (2) compute the length of the tour, and (3) compare the length of the tour to the given number.
So, you build a new machine. This machine is like the old machine, except it is fitted with a guessing module that has its own write-only head. In the first stage of the operation of the machine, the write-only head writes symbols on tape squares. In the second stage of the operation of the machine, the read-write head checks the symbols that the write-only head wrote. The machine solves the problem if:
(1) For every instance of the problem whose answer is “yes”, there is some guess that leads the checking stage to enter a yes-state, and
(2) For every instance of the problem whose answer is not “yes”, there is no guess that leads the checking stage to enter a yes-state.
A problem that this new machine can solve in polynomial time belongs to a class of problems called NP.
Your new machine can solve in polynomial time all the problems that your first machine can solve in polynomial time. Just ignore any guess made during the guessing stage, and during the checking stage perform the operation of the first machine. So, every problem that belongs to P also belongs to NP.
But can your first machine solve in polynomial time every problem that your new machine can solve in polynomial time? If it can, then P=NP.
It would be great if P=NP, because then seemingly hard problems, like the second problem that your manager gave you, would have fast solutions, like the first problem that your manager gave you. However, it is widely believed that P!=NP.
Garey, Michael R., and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman, 1979.