Computational Complexity of Problems with Digraphs and Finite Topological Spaces

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

Full text not available from this repository. (Request a copy)

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


© FortWorks - powered by EPrints 3 - sponsored and maintained by the John F. Reed Library at Fort Lewis College