Knottedness is in NP, modulo GRH

DOI10.1016/j.aim.2014.01.007zbMath1358.68138arXiv1112.0845OpenAlexW2964047222MaRDI QIDQ2445896

Greg Kuperberg

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

zbMATH Keywords

generalized Riemann hypothesisNPknottednesspolynomial-length certificate

Mathematics Subject Classification ID

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

• ECPP

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