NP - Complete Problems, Turing Machines, And The Proof Of Cook's Theorem

Abstract

here exists a group of practical problems in computer science today for which no one has yet been able to find reasonable algorithmic solutions (those solvable in a reasonable amount of time), yet no one has been able to prove that no such solutions exist, either. These problems readily admit naive, or obvious solutions, but these solutions would take entirely unreasonable amounts of time, say thousands of years, to terminate. Scientists have simply not been able to find other algorithms that run faster and more efficiently, but, as noted, have also been unable to prove their nonexistence. This puzzle has teased computer scientists for decades now, and it continues to be of great interest. Why are these problems so important? There are approximately 1000 problems known to fall into this uncertainty category1, and most of them have many practical uses. For example, if we could solve the Traveling Salesman problem, we could immediately map out the most efficient route for delivery companies such as UPS or Federal Express. If we could figure out the Bin Packing problem, lumber yards would be able to more efficiently fill orders from large pieces of wood. Being able to solve the Graph Coloring problem would make scheduling final exams for a university much quicker and easier. These problems are discussed in length in the pages that follow. One of the most interesting aspects of these problems is that if scientists could find a fast running algorithm to solve any one of this special category of problems, they would know that a fast algorithm necessarily exists for all of them! Conversely, if they could prove that no such algorithm exists for one of them, they would know that there will never be a fast algorithm to solve any of them, and they could concentrate their efforts on finding algorithms to approximate the solutions. This class of problems, commonly called NPcomplete problems, will be a major topic of this paper. Turing machines, which will be the second focus of this paper, play a unique role in the development of these NP-complete problems. It is through these theoretical machines that the computation process has been separated into its most basic elements. Stephen A. Cook used the theory of Turing machines to prove his landmark theorem, which established the existence of an actual NP-complete problem. In the third section, I will present and prove Cook's Theorem, and to conclude the paper I will pull many of these ideas together by presenting three reductions between various pairs of NP-complete problems.