Abstract
The easiest hard problem: phase transitions in integer partitioning
Stephan Mertens
University of Magdeburg, Germany
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.
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.
No video available