Phase transitions in integer linear problems Journal Article

Author(s): Colabrese, Simona; De Martino, Daniele; Leuzzi, Luca; Marinari, Enzo
Article Title: Phase transitions in integer linear problems
Affiliation IST Austria
Abstract: The resolution of a linear system with positive integer variables is a basic yet difficult computational problem with many applications. We consider sparse uncorrelated random systems parametrised by the density c and the ratio α = N/M between number of variables N and number of constraints M. By means of ensemble calculations we show that the space of feasible solutions endows a Van-Der-Waals phase diagram in the plane (c, α). We give numerical evidence that the associated computational problems become more difficult across the critical point and in particular in the coexistence region.
Keywords: Classical phase transitions; typical-case computational complexity
Journal Title: Journal of Statistical Mechanics: Theory and Experiment
Volume: 2017
Publisher: IOPscience  
Date Published: 2017-09-26
Start Page: Article number: 093404
Sponsor: The research leading to these results has received funding from the People Programme ( Marie Curie Actions ) of the European Union ’ s Seventh Framework Programme ( FP 7 / 2007 − 2013 ) under REA grant agreement n [291734] ( DDM ) .
DOI: 10.1088/1742-5468/aa85c3
Notes: DDM would like to thank Alexandr Kazda and Davide Raimondo for interesting discussions.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work