Masters Theses
Date of Award
8-2007
Degree Type
Thesis
Degree Name
Master of Science
Major
Mathematics
Major Professor
James Conant
Committee Members
David Anderson, Conrad Plaut
Abstract
It is the purpose of this thesis to introduce an idea for studying questions of computer science via topology. We begin by describing the homology of a certain space constructed from a given subset of the power set of any finite set. We then discuss how this relates to the k-SAT problem in computer science.
We shall use computers as a tool to calculate the homology groups as well as the Euler characteristic of some of these spaces. Due to the sheer number of calcu- lations needed, doing the necessary computations by hand is both impractical and impossible.
In addition, with inspiration from these results, we will provide several rigorous mathematical proofs detailing certain properties of the spaces produced by some input sets.
Recommended Citation
Thistlethwaite, Oliver J., "A Study of the Homology of Subset Spaces and their Connection to the K-SAT Problem in Computer Science. " Master's Thesis, University of Tennessee, 2007.
https://trace.tennessee.edu/utk_gradthes/228