Symposium on Discrete Algorithms (SODA) 2001, pp. 721-722.
It is well known that random instances of 3-SAT undergo a phase transition between satisfiability and unsatisfiability when the ratio c of clauses to variables passes a critical value. Here we consider 3-SAT's variants, 1-in-3 SAT and more generally 1-in-k SAT, and NAESAT.
For 1-in-3 SAT, in which exactly one literal in each clause must be true, we show that the phase transition occurs exactly at c=1/3 and more generally that 1-in-k SAT has a transition at 2/(k(k-1)). This is the first example of an NP-complete problem in this family for which we can identify the threshold exactly.
Our results also establish that the phase transition in 1-in-k SAT is second-order, contradicting the conjecture that NP-complete problems have first-order phase transitions. In fact, we suggest that it is in the same universality class as 2-SAT, since both of these are essentially percolation in random directed graphs.
For NAESAT, we prove bounds on the location of the phase transition of 1.514 <= c <= 2.214, and provide a numerical estimate of 2.1. Interestingly, some of the best methods for proving lower bounds for 3-SAT do not apply to NAESAT, and our lower bound relies on a novel approach which minimizes the flow of 2-SAT clauses into unit clauses.
(Note: in this paper we criticize a paper of Monasson et al., saying that they had conjectured that NP-complete problems have first-order phase transitions. In fact, we misunderstood their paper; their conjecture is, rather, that NP-complete problems with exponential typical-case complexity have first-order transitions, and they indeed gave an example of an NP-complete problem that has a second-order (2-SAT-like) transition, namely (2+p)-SAT where p < 2/5. Thus our results are consistent with their conjecture.)