On the thresholds in linear and nonlinear Boolean equations

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.