• Login
    View Item 
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    1990_BrunkenL_THS_000594.pdf (4.928Mb)
    Author
    Brunken, Laura
    Advisor
    Philip Rose; Darrel Hagen; Marie Vanisko
    Date of Issue
    1990-04-01
    Metadata
    Show full item record
    URI
    https://scholars.carroll.edu/handle/20.500.12647/3475
    Title
    NP - Complete Problems, Turing Machines, And The Proof Of Cook's Theorem
    Type
    thesis
    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.
    Degree Awarded
    Bachelor's
    Semester
    Spring
    Department
    Mathematics, Engineering & Computer Science
    Collections
    • Mathematics, Engineering and Computer Science Undergraduate Theses

    Browse

    All of Carroll ScholarsCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV