Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers
arXiv:1304.0204 · doi:10.4036/iis.2013.51
Abstract
We propose a new formulation of the problem of prime factorization of integers. With replica exchange Monte Carlo simulation, the behavior which is seemed to indicate exponential computational hardness is observed. But this formulation is expected to give a new insight into the computational complexity of this problem from a statistical mechanical point of view.
arXiv comment5 pages, 5figures, Proceedings of 4th YSM-SPIP (Sendai, 14-16 December 2012)
References in corpus (9)
- 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
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
- Spin glasses in the non-extensive regime
- Ensemble Inequivalence and the Spin-Glass Transition
- Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
- Many-body spin glasses in the microcanonical ensemble