The Easiest Hard Problem: Number Partitioning

Details The Easiest Hard Problem: Number Partitioning The Easiest Hard Problem: Number Partitioning

2003-10-14

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

Physics

Condensed Matter

Disordered Systems and Neural Networks

8 pages, to appear in A.G. Percus, G. Istrate and C. Moore, eds., Computational Complexity and Statistical Physics (Oxford Uni

Scientific paper

Number partitioning is one of the classical NP-hard problems of combinatorial optimization. It has applications in areas like public key encryption and task scheduling. The random version of number partitioning has an "easy-hard" phase transition similar to the phase transitions observed in other combinatorial problems like $k$-SAT. In contrast to most other problems, number partitioning is simple enough to obtain detailled and rigorous results on the "hard" and "easy" phase and the transition that separates them. We review the known results on random integer partitioning, give a very simple derivation of the phase transition and discuss the algorithmic implications of both phases.

Affiliated with

Also associated with

No associations

Rating

The Easiest Hard Problem: Number Partitioning 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 The Easiest Hard Problem: Number Partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Easiest Hard Problem: Number Partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-428288