Tricritical Points in Random Combinatorics: the (2+p)-SAT case

Abstract

The (2+p)-Satisfiability (SAT) problem interpolates between different classes of complexity theory and is believed to be of basic interest in understanding the onset of typical case complexity in random combinatorics. In this paper, a tricritical point in the phase diagram of the random $2+p$-SAT problem is analytically computed using the replica approach and found to lie in the range $2/5\le p_0\le 0.416$. These bounds on $p_0$ are in agreement with previous numerical simulations and rigorous results.

7 pages, 1 figure, RevTeX, to appear in J.Phys.A

References in corpus (1)

• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses

Cited by in corpus (12)

• Entropies of complex networks with hierarchically constrained topologies
• Finite Connectivity Attractor Neural Networks
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Replicated Transfer Matrix Analysis of Ising Spin Models on `Small World' Lattices
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Phase coexistence and finite-size scaling in random combinatorial problems
• Relaxation in graph coloring and satisfiability problems
• Finitely connected vector spin systems with random matrix interactions
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
• Spin models on random graphs with controlled topologies beyond degree constraints
• Blume-Emery-Griffiths model on Random Graphs