A Study of the Homology of Subset Spaces and their Connection to the K-SAT Problem in Computer Science
Date of Award
Master of Science
David Anderson, Conrad Plaut
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.
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.