Phase transitions in integer linear problems

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.

arXiv comment15 pages, 6 figures, comments are welcome

References in corpus (8)

• Statistical mechanics of the random K-SAT model
• Phase Transition in the Number Partitioning Problem
• The simplest model of jamming
• Counting and correcting thermodynamically infeasible flux cycles in genome-scale metabolic networks
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• The dual of the space of interactions in neural network models
• The K-sat problem in a simple limit

Cited by in corpus (1)

• On non-negative solutions to large systems of random linear equations