FPRAS hardness conjecture for Jones polynomial evaluation
FPRAS hardness conjecture for Jones polynomial evaluation
For an integer with , let , and let denote the Jones polynomial of a link evaluated at . An FPRAS is a fully polynomial randomized approximation scheme, and and are the standard randomized and nondeterministic polynomial-time complexity classes.
Jones-polynomial FPRAS conjecture. There is no FPRAS for evaluating except at the special points , provided .
At the exceptional points the Jones polynomial degenerates to a classical link invariant computable in polynomial time, whereas exact evaluation is -hard at the other roots of unity described in the paper. The conjecture concerns the stronger approximation-complexity question.
Sources & referencesView supporting material
Primary source
Eric C. Rowell, “Two paradigms for topological quantum computation”, arXiv:0803.1258 (2008).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.