First Advisor

Oscar Levin

Degree Name

Bachelor of Science

Document Type

Thesis

Date Created

12-2024

Department

College of Natural and Health Sciences, Mathematical Sciences, Mathematical Sciences Student Work

Abstract

There is a long-standing problem in the mathematical world known as the P vs NP problem which relates to how we classify math problems. Problems in P are problems that are easy to solve and verify relatively quick whereas and NP are quick to verify, but it is unknown how easy or hard it is to solve quickly. We will discuss what it means to be solved quickly later on. Moving to the next classification, NP is either is equal to P, which would inherently make all P problems equal to NP-Complete, or P is simply not equal to NP. NP-Complete is another way to classify a problem, just like NP and P. A problem is NP-Complete if that problem is in NP and can be transformed into every other problem in NP. While all NP-complete problems are about finite structures, many of these problems can be extended to infinite versions. However, even though the finite versions are all equally ”hard”, the corresponding infinite versions can vary in complexity. We created proofs of reductions from three specific NP-Complete problems: independent set, clique, and vertex cover. Independent set is given a graph, G, there is a set, S, of vertices where no two are adjacent. Clique consists of a set of k vertices all adjacent to each other. Vertex cover is where there is a set of vertices from graph G where all the edges are accounted for due to the extensions from the vertices in the set. We have created reductions from these NP-Complete problems into one another in both the finite and infinite case. Since all of these are NP-Complete problems and thus in NP, showing we can reduce them into one another will aid in our understanding of why they behave differently in infinite as well as providing information about the NP-Complete class to aid the P vs. NP problem.

Abstract Format

html

Keywords

Graph Theory

Language

English

Extent

16 pages

Rights Statement

Copyright is held by the author.

Download

Share

COinS