Hiding solutions in random satisfiability problems: A statistical mechanics approach

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 (3SAT). 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.

5 pages, 4 figures, revised version to app. in PRL

References in corpus (2)

• Simplest random K-satisfiability problem
• Exact solutions for diluted spin glasses and optimization problems

Cited by in corpus (51)

• Statistical physics of inference: Thresholds and algorithms
• Probing for quantum speedup in spin glass problems with planted solutions
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Quantum Annealing Correction with Minor Embedding
• A Simple Model to Generate Hard Satisfiable Instances
• Constraint satisfaction problems with isolated solutions are hard
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Typology of phase transitions in Bayesian inference problems
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Random Graph Coloring - a Statistical Physics Approach
• Practical engineering of hard spin-glass instances
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Directed percolation and numerical stability of simulations of digital memcomputing machines
• Advantages of Unfair Quantum Ground-State Sampling
• Hiding Satisfying Assignments: Two are Better than One
• Equation Planting: A Tool for Benchmarking Ising Machines
• Computational hardness of spin-glass problems with tile-planted solutions
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Estimating the Density of States of Frustrated Spin Systems
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Solution space structure of random constraint satisfaction problems with growing domains
• Hardware implementation of digital memcomputing on small-size FPGAs
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Fully parallel implementation of digital memcomputing on FPGA
• Non-equilibrium criticality and efficient exploration of glassy landscapes with memory dynamics
• Self-planting: digging holes in rough landscapes
• Posiform Planting: Generating QUBO Instances for Benchmarking
• The solution space structure of planted constraint satisfaction problems with growing domains
• Asymptotic Exceptional Steady States in Dissipative Dynamics
• From spin glasses to hard satisfiable formulas
• Entropy and chirality in sphinx tilings
• Tensor networks for $p$-spin models
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Finite-size scaling in random $K$-satisfiability problems
• Hiding solutions in model RB: Forced instances are almost as hard as unforced ones
• Acceleration of digital memcomputing by jumps
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
• On the solvable-unsolvable transition due to noise-induced chaos in digital memcomputing