Related Experiment Video
Updated: Oct 1, 2026

Computation of Atmospheric Concentrations of Molecular Clusters from ab initio Thermochemistry
Published on: April 8, 2020
Hiding solutions in random satisfiability problems: a statistical mechanics approach
W Barthel1, A K Hartmann, M Leone
1Institute for Theoretical Physics, University of Göttingen, Bunsenstrasse 9, 37073 Göttingen, Germany.
Abstract:
A major problem in evaluating stochastic local search algorithms for NP-complete problems is the need for a systematic generation of hard test instances having previously known properties of the optimal solutions. On the basis of statistical mechanics results, we propose random generators of hard and satisfiable instances for the 3-satisfiability problem. The design of the hardest problem instances is based on the existence of a first order ferromagnetic phase transition and the glassy nature of excited states. The analytical predictions are corroborated by numerical results obtained from complete as well as stochastic local algorithms.
Related Concept Videos
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Solution Formation
This selective solubility...
Entropy and Solvation
Mechanistic Models: Compartment Models in Individual and Population Analysis
Alternative Sets of Equilibrium Equations
One example of such a situation can be observed in a...
Biot-Savart Law: Problem-Solving
Consider a mobile phone battery bank as a source of steady current, which flows through the wire connected between the two. What is the magnitude of the magnetic field created by this current at a field point P?
To estimate the magnitude of the total magnetic field, we first consider a small current element of length dl, at a distance r from the field point. Now the following...
