Browsing OSU - Faculty Papers by Subject "68Q25: Analysis of algorithms and problem complexity"

Now showing items 1-2 of 2

    • On the complexity of cusped non-hyperbolicity 

      Haraway, Robert, III; Hoffman, Neil R. (2019-07-02)
      We show that the problem of showing that a cusped 3-manifold M is not hyperbolic is in NP, assuming S3-RECOGNITION is in coNP. To this end, we show that IRREDUCIBLE TOROIDAL RECOGNITION lies in NP. Along the way we ...

    • Small PSL(2,F) representations of Seifert fiber space groups 

      Hoffman, Neil R.; Petersen, Kathleen L. (2022-09-12)
      Let M be a Seifert fiber space with non-abelian fundamental group and admitting a triangulation with t tetrahedra. We show that there is a non-abelian PSL(2,F) quotient where |F|<c(220t3120t) for an absolute constant c>0 ...