Knottedness is in NP, modulo GRH
From MaRDI portal
Publication:2445896
DOI10.1016/j.aim.2014.01.007zbMath1358.68138arXiv1112.0845OpenAlexW2964047222MaRDI QIDQ2445896
Publication date: 15 April 2014
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.0845
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (18)
Rectangular knot diagrams classification with deep learning ⋮ On Jones' subgroup of R. Thompson group \(F\) ⋮ Integer homology 3-spheres admit irreducible representations in \(\mathrm{SL}(2,{\mathbb C})\) ⋮ Models of random knots ⋮ The unbearable hardness of unknotting ⋮ Some conditionally hard problems on links and 3-manifolds ⋮ Computing Heegaard Genus is NP-Hard ⋮ On meridian-traceless \(\mathrm{SU}(2)\)-representations of link groups ⋮ A polynomial upper bound on Reidemeister moves ⋮ Identifying lens spaces in polynomial time ⋮ Unnamed Item ⋮ Simply connected latin quandles ⋮ The efficient certification of knottedness and Thurston norm ⋮ Shellings from relative shellings, with an application to NP-completeness ⋮ Unnamed Item ⋮ Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT ⋮ Detecting Unknots via Equational Reasoning, I: Exploration ⋮ On the complexity of torus knot recognition
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Probabilistic algorithm for testing primality
- Riemann's hypothesis and tests for primality
- Dehn surgery, the fundamental group and \(\operatorname{SU}(2)\)
- PRIMES is in P
- Simulation of topological field theories by quantum computers
- On relationships between statistical zero-knowledge proofs
- Quantifying residual finiteness.
- Extremal behavior of divisibility functions.
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- Noncyclic covers of knot complements
- Elliptic Curves and Primality Proving
- The computational complexity of knot and link problems
- Primality testing using elliptic curves
- Finding the number of factors of a polynomial
- Every Prime Has a Succinct Certificate
- A note on the complexity of cryptography (Corresp.)
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- On the faithful representation of infinite groups by matrices
- A polynomial quantum algorithm for approximating the Jones polynomial
This page was built for publication: Knottedness is in NP, modulo GRH
