On the complexity and combinatorics of covering finite complexes.
James M. Abello, Michael R. Fellows, John Stillwell · 1991
Some aspects of the theory and computational complexity of covering projections of finite complexes are considered, from both the combinatorial and topological perspectives. The relationship between these two perspectives is explored. It is shown that there are l-complexes Y for which the computational decision problem which takes input finite I-complex X and determines if X covers Y is NP-complete for both simplicial (combinatorial) and topological covering projections. A theorem of Leighton concerning finite common covers of I-complexes, which holds both c.ornbinatorially and topologically, is shown to fail topologically for 2-complpxes. Some reiiUlts concerning I-complexes which are mutual covers are also presented. The discussion is intended to be accessible to both combinatorialists and topologists.