The number of solutions for random regular NAE-SAT

Understand

Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems.

• In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions of statistical physics.
• Here we revisit one of these models, random regular k-NAE-SAT: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance.
• We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction.