Eur. Phys. J. B 76, 123-146 (2010)
https://doi.org/10.1140/epjb/e2010-00173-7

On the thresholds in linear and nonlinear Boolean equations

LMIB and School of Mathematics and Systems Science, Beihang University, 100191, Beijing, P.R. China

Corresponding author: ^a sunyifan@ss.buaa.edu.cn

Received: 8 February 2010
Revised: 5 April 2010
Published online: 10 June 2010

Abstract

We introduce a generalized XORSAT model, named as Massive Algebraic System (Hereafter abbreviated as MAS) consisting of linear and nonlinear Boolean equations. Through adjusting the proportion of nonlinear equations, denoted by p, this MAS model smoothly interpolates between XORSAT (p = 0) and MAS-nonlinear (p = 1). We conduct a systematic and complete study about a series of phase transitions in the space of solutions at given p and also present how the phase diagram evolves with the increase of p. First of all, using the probabilistic method and energetic 1RSB cavity method, we compute the satisfiability thresholds for any given p ∈ [0,1) and determine a region where the satisfaction of problem all depends on its subproblem MAS-nonlinear. Furthermore, we locate three important non-satisfiability transitions, i.e. clustering, condensation and freezing, using entropic 1RSB cavity method, and find the space of solution undergoing different phase transition processes with the increase of p.