The Phase Diagram of 1-in-3 Satisfiability Problem

Abstract

We study the typical case properties of the 1-in-3 satisfiability problem, the boolean satisfaction problem where a clause is satisfied by exactly one literal, in an enlarged random ensemble parametrized by average connectivity and probability of negation of a variable in a clause. Random 1-in-3 Satisfiability and Exact 3-Cover are special cases of this ensemble. We interpolate between these cases from a region where satisfiability can be typically decided for all connectivities in polynomial time to a region where deciding satisfiability is hard, in some interval of connectivities. We derive several rigorous results in the first region, and develop the one-step--replica-symmetry-breaking cavity analysis in the second one. We discuss the prediction for the transition between the almost surely satisfiable and the almost surely unsatisfiable phase, and other structural properties of the phase diagram, in light of cavity method results.

30 pages, 12 figures

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• The cavity method at zero temperature
• Alternative solutions to diluted p-spin models and XORSAT problems
• Approximating satisfiability transition by suppressing fluctuations

Cited by in corpus (17)

• Anderson localization casts clouds over adiabatic quantum optimization
• First order phase transition in the Quantum Adiabatic Algorithm
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Constraint satisfaction problems with isolated solutions are hard
• Quantum algorithm for energy matching in hard optimization problems
• Fast counting with tensor networks
• Sparsely-spread CDMA - a statistical mechanics based analysis
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• Statistical mechanics of budget-constrained auctions
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Decimation flows in constraint satisfaction problems
• A journey into localization, integrability and thermalization
• Counting with the quantum alternating operator ansatz
• q-Overlaps in the Random Exact Cover Problem