Groh, Christine and Yarbrough, Patrick (2014) *Computational Complexity of Problems with Digraphs and Finite Topological Spaces.* [Abstract]

## Abstract

Consider a finite topological space X. By using the relationship between digraphs and finite topological spaces, a corresponding digraph, GX can be found. Then, completing the adjacency matrix for GX can be used to determine the complexity class (defined via Turing machines) of problems involving GX, and therefore of X as well. This talk will examine the complexity classes of problems in deciding whether spaces are self-complementary finite topological spaces, deformation retracts, and if a finite topological space is a T0-space.

Item Type: | Abstract |
---|---|

Created by Student or Faculty: | Student |

Uncontrolled Keywords: | Computational complexity, topological spaces, finite topological spaces, topology, digraphs, transitive digraphs, Turing machine, P versus NP, bijective correspondence, T0 space, adjacency matrix, deformation retracts |

Subjects: | Undergrad Research Symposium > Mathematics Undergrad Research Symposium |

Depositing User: | Christine Groh |

Date Deposited: | 16 Apr 2014 16:14 |

Last Modified: | 17 Apr 2014 09:37 |

URI: | http://fortworks.fortlewis.edu/id/eprint/531 |