The easiest hard problem: phase transitions in integer partitioning

Stephan Mertens
University of Magdeburg, Germany
Inst. f. Theor. Physics

Integer partitioning is one of the classical NP-hard problems.
The random version of integer partitioning has a phasetransition
similar to the phasetransitions observed in other combinatorial
problems like k-SAT. In contrast to most other problems, integer
partitioning is simple enough to obtain detailled and rigorous
results on the phasetransition. In this talk we discuss the
phasediagramm of constrained integer partitioning.

Presentation (PDF File)

Back to Phase Transitions And Algorithmic Complexity