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

Phase transitions in integer linear problems / Colabrese, S.; De Martino, D.; Leuzzi, L.; Marinari, E.. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - STAMPA. - 2017:9(2017), p. 093404. [10.1088/1742-5468/aa85c3]

Phase transitions in integer linear problems

Marinari, E.
2017

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
2017
classical phase transitions; typical-case computational complexity; Statistical and Nonlinear Physics; Statistics and Probability; Statistics, Probability and Uncertainty
01 Pubblicazione su rivista::01a Articolo in rivista
Phase transitions in integer linear problems / Colabrese, S.; De Martino, D.; Leuzzi, L.; Marinari, E.. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - STAMPA. - 2017:9(2017), p. 093404. [10.1088/1742-5468/aa85c3]
File allegati a questo prodotto
File Dimensione Formato  
Colabrese_Phase_2017.pdf

solo gestori archivio

Note: Articolo pubblicato.
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.16 MB
Formato Adobe PDF
1.16 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1020830
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact