Statistical Mechanics of an NP-complete Problem: Subset Sum

Details Statistical Mechanics of an NP-complete Problem: Subset Sum Statistical Mechanics of an NP-complete Problem: Subset Sum

2001-06-07

arxiv.org/abs/cond-mat/0106125v2

J. Phys. A: Math. Gen. 34 (2001) 9555-9567

Physics

Condensed Matter

Statistical Mechanics

17 pages, 2 figures

Scientific paper

10.1088/0305-4470/34/44/314

We study statistical properties of an NP-complete problem, the subset sum, using the methods and concepts of statistical mechanics. The problem is a generalization of the number partitioning problem, which is also an NP-complete problem and has been studied in the physics literature. The asymptotic expressions for the number of solutions are obtained. These results applied to the number partitioning problem as a special case are compared with those which were previously obtained by a different method. We discuss the limit of applicability of the techniques of statistical mechanics to the present problem.

Affiliated with

Also associated with

No associations

Rating

Statistical Mechanics of an NP-complete Problem: Subset Sum 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 Statistical Mechanics of an NP-complete Problem: Subset Sum, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Mechanics of an NP-complete Problem: Subset Sum will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-459192