Phase transition and computational complexity in a stochastic prime number generator

Details Phase transition and computational complexity in a stochastic prime number generator Phase transition and computational complexity in a stochastic prime number generator

2007-12-19

arxiv.org/abs/0712.3137v1

New Journal of Physics 10 (2008) 023009

Computer Science

Computational Complexity

Submitted to New Journal of Physics

Scientific paper

10.1088/1367-2630/10/2/023009

We introduce a prime number generator in the form of a stochastic algorithm. The character of such algorithm gives rise to a continuous phase transition which distinguishes a phase where the algorithm is able to reduce the whole system of numbers into primes and a phase where the system reaches a frozen state with low prime density. In this paper we firstly pretend to give a broad characterization of this phase transition, both in terms of analytical and numerical analysis. Critical exponents are calculated, and data collapse is provided. Further on we redefine the model as a search problem, fitting it in the hallmark of computational complexity theory. We suggest that the system belongs to the class NP. The computational cost is maximal around the threshold, as common in many algorithmic phase transitions, revealing the presence of an easy-hard-easy pattern. We finally relate the nature of the phase transition to an average-case classification of the problem.

Affiliated with

Also associated with

No associations

Rating

Phase transition and computational complexity in a stochastic prime number generator does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase transition and computational complexity in a stochastic prime number generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase transition and computational complexity in a stochastic prime number generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-146413