Europhys. Lett.
Volume 72, Number 5, December 2005
Page(s) 691 - 697
Section General
Published online 26 October 2005
Europhys. Lett., 72 (5), pp. 691-697 (2005)
DOI: 10.1209/epl/i2005-10296-6

Phase transition in the assignment problem for random matrices

J. G. Esteve and F. Falceto

Departamento de Física Teórica, Universidad de Zaragoza - Zaragoza, Spain and Instituto de Biocomputación y Física de Sistemas Complejos, Universidad de Zaragoza Zaragoza, Spain

received 6 July 2005; accepted in final form 30 September 2005
published online 26 October 2005

We report an analytic and numerical study of a phase transition in a P problem (the assignment problem) that separates two phases whose representatives are the simple matching problem (an easy P problem) and the traveling-salesman problem (a NP-complete problem). Like other phase transitions found in combinatoric problems (K-satisfiability, number partitioning) this can help to understand the nature of the difficulties in solving NP problems an to find more accurate algorithms for them.

02.60.Pn - Numerical optimization.
02.70.Rr - General statistical methods.
64.60.Cn - Order-disorder transformations; statistical mechanics of model systems.

© EDP Sciences 2005