Computing a Knot Invariant as a Constraint Satisfaction Problem
arXiv:1111.1060 · doi:10.1143/JPSJ.81.035001
Abstract
We point out the connection between mathematical knot theory and spin glass/search problem. In particular, we present a statistical mechanical formulation of the problem of computing a knot invariant; p-colorability problem, which provides an algorithm to find the solution. The method also allows one to get some deeper insight into the structural complexity of knots, which is expected to be related with the landscape structure of constraint satisfaction problem.
arXiv comment6 pages, 3 figures, submitted to short note in Journal of Physical Society of Japan
References in corpus (8)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Phase Transitions in the Coloring of Random Graphs
- Coloring random graphs
- On the freezing of variables in random constraint satisfaction problems
- Constraint satisfaction problems with isolated solutions are hard
- Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
- Numerical Solution-Space Analysis of Satisfiability Problems