Recognition of Seifert fibered spaces with boundary is in NP
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909231304671232 |
|---|---|
| author | Jackson, Adele |
| author_facet | Jackson, Adele |
| contents | We show that the decision problem of recognising whether a triangulated 3-manifold admits a Seifert fibered structure with non-empty boundary is in NP. We also show that the problem of producing Seifert data for a triangulation of such a manifold is in the complexity class FNP. We do this by proving that in any triangulation of a Seifert fibered space with boundary there is both a fundamental horizontal surface of small degree and a complete collection of normal vertical annuli whose total weight is bounded by an exponential in the square of the triangulation size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_04612 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Recognition of Seifert fibered spaces with boundary is in NP Jackson, Adele Geometric Topology Computational Complexity Computational Geometry 57-08, 57K30, 57K35, 57Q15, 68Q25 We show that the decision problem of recognising whether a triangulated 3-manifold admits a Seifert fibered structure with non-empty boundary is in NP. We also show that the problem of producing Seifert data for a triangulation of such a manifold is in the complexity class FNP. We do this by proving that in any triangulation of a Seifert fibered space with boundary there is both a fundamental horizontal surface of small degree and a complete collection of normal vertical annuli whose total weight is bounded by an exponential in the square of the triangulation size. |
| title | Recognition of Seifert fibered spaces with boundary is in NP |
| topic | Geometric Topology Computational Complexity Computational Geometry 57-08, 57K30, 57K35, 57Q15, 68Q25 |
| url | https://arxiv.org/abs/2306.04612 |