Phase transitions in integer linear problems

DOI10.1088/1742-5468/AA85C3MaRDI QIDQ3303199zbMATH OpenOpenAlexFDO

Authors S. Colabrese, D. De Martino, Luca Leuzzi, Enzo Marinari

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.06303

Mathematics Subject Classification ID

Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: The resolution of 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 $alpha=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$, $alpha$). We give numerical evidence that the associated computational problems become more difficult across the critical point and in particular in the coexistence region.

Recommendations

• scientific article; zbMATH DE number 2084721
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• An empirical study of phase transitions in binary constraint satisfaction problems
• Locating the phase transition in binary constraint satisfaction problems
• scientific article; zbMATH DE number 2046061

Cites work

• Complexity transitions in global algorithms for sparse linear systems over finite fields
• Computation of Modified Bessel Functions and Their Ratios
• Determining computational complexity from characteristic ``phase transitions
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Information, Physics, and Computation
• Integer points in polyhedra
• Integer Programming with a Fixed Number of Variables
• Phase Transition in the Number Partitioning Problem
• Statistical mechanics methods and phase transitions in optimization problems
• The 3-SAT problem with large number of clauses in the ∞-replica symmetry breaking scheme
• The K-SAT problem in a simple limit
• The simplest model of jamming
• The space of interactions in neural network models

Cited in

(6)

• On non-negative solutions to large systems of random linear equations
• Phase transitions in semidefinite relaxations
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• scientific article; zbMATH DE number 2084721 (Why is no real title available?)
• scientific article; zbMATH DE number 868179 (Why is no real title available?)
• scientific article; zbMATH DE number 6469137 (Why is no real title available?)

This page was built for publication: Phase transitions in integer linear problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303199)