On the complexity and combinatorics of covering finite complexes.

*(English)*Zbl 0763.05035The computational complexity of covering projections of finite complexes is considered. As the main result, it is proved that there exist graphs (that is, 1-complexes) \(H\) for which the decision problem which takes as input a finite graph \(G\) and determines if there is a covering projection of \(H\) by \(G\) is NP-complete (both in simplicial as well as in topological setting). This is interesting because the existence of a covering projection establishes a “local isomorphism” between graphs, and so the problem of its detecting seems to be substantially different from isomorphism testing. Some results on pairs of infinite 1-complexes that are each other’s covering spaces are included.

Reviewer: A.Rosa (Hamilton / Ontario)