Phase Transition in the Number Partitioning Problem

Abstract

Number partitioning is an NP-complete problem of combinatorial optimization. A statistical mechanics analysis reveals the existence of a phase transition that separates the easy from the hard to solve instances and that reflects the pseudo-polynomiality of number partitioning. The phase diagram and the value of the typical ground state energy are calculated.

minor changes (references, typos and discussion of results)

References in corpus (1)

• Probabilistic Analysis of the Number Partitioning Problem

Cited by in corpus (62)

• Adiabatic Quantum Computing
• What is the Computational Value of Finite Range Tunneling?
• Photon-Mediated Spin-Exchange Dynamics of Spin-1 Atoms
• Typical random 3-SAT formulae and the satisfiability threshold
• Physics of the Riemann Hypothesis
• Random Costs in Combinatorial Optimization
• Exact solutions for diluted spin glasses and optimization problems
• Robust quantum optimizer with full connectivity
• A physicist's approach to number partitioning
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
• Scalable spin-glass optical simulator
• Experimental Observation of Phase Transitions in Spatial Photonic Ising Machine
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Universality in the level statistics of disordered systems
• Quantum annealing for the number partitioning problem using a tunable spin glass of ions
• Number partitioning as random energy model
• Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
• Dicke simulators with emergent collective quantum computational abilities
• Optimal combinations of imperfect objects
• Relaxation in graph coloring and satisfiability problems
• Antiferromagnetic spatial photonic Ising machine through optoelectronic correlation computing
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Clustering analysis of the ground-state structure of the vertex-cover problem
• On Minimum Violations Ranking in Paired Comparisons
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• Fast optimization algorithms and the cosmological constant
• Asymptotics of the number partitioning distribution
• Factorising numbers with a Bose-Einstein condensate
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Statistical Mechanics of an NP-complete Problem: Subset Sum
• Phase transition and landscape statistics of the number partitioning problem
• Phase Transition in Multiprocessor Scheduling
• Approximate analysis of search algorithms with "physical" methods
• Local energy statistics in disordered systems: a proof of the local REM conjecture
• A complete anytime algorithm for balanced number partitioning
• Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
• The stability to instability transition in the structure of large scale networks
• Simulations of the adiabatic quantum optimization for the Set Partition Problem
• Computational Complexity and Phase Transitions
• Number Partitioning on a Quantum Computer
• Criticality of natural absorbing states
• Solution-space structure of (some) optimization problems
• Statistical Mechanics Analysis of the Continuous Number Partitioning Problem
• On a dynamical approach to some prime number sequences
• Entropy-based analysis of the number partitioning problem
• Phase transition in a stochastic prime number generator
• Topologically protected Grover's oracle for the partition problem
• Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
• On the fluctuations of the number of atoms in the condensate
• Computational Complexity for Physicists
• Polynomial Observables in the Graph Partitioning Problem
• Taking a shower in Youth Hostels: risks and delights of heterogeneity
• Phase transitions in Number Theory: from the Birthday Problem to Sidon Sets
• Hard combinatorial problems and minor embeddings on lattice graphs
• Phase transition in the bipartite z-matching
• Phase transition in the assignment problem for random matrices
• Phase transitions in integer linear problems
• Instance Space of the Number Partitioning Problem
• Local Energy Statistics in Directed Polymers
• Statistical mechanical models of integer factorization problem