Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT

Abstract

We determine the complexity of several constraint satisfaction problems using the heuristic algorithm, WalkSAT. At large sizes N, the complexity increases exponentially with N in all cases. Perhaps surprisingly, out of all the models studied, the hardest for WalkSAT is the one for which there is a polynomial time algorithm.

5 pages, 4 figures

References in corpus (3)

• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard

Cited by in corpus (17)

• Adiabatic Quantum Computing
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Driver Hamiltonians for constrained optimization in quantum annealing
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Equation Planting: A Tool for Benchmarking Ising Machines
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Leveraging Analog Quantum Computing with Neutral Atoms for Solvent Configuration Prediction in Drug Discovery
• Obstacles to quantum annealing in a planar embedding of XORSAT
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Tensor networks for $p$-spin models
• Inside the clustering threshold for random linear equations
• Inside the clustering window for random linear equations
• Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm