Random k-NAE: Satisfying a Proportion of Clauses and an Algorithmic Barrier

Abstract

A random k-CNF formula with m clauses and n variables, denoted F_k(n, m), is said to be p-satisfiable in the NAE (Not-All-Equal) sense if there exists a variable assignment such that a proportion of at least 1 − 2^{1−k} + p2^{1−k} of the formula’s clauses have at least one true and one false literal under the assignment. In this thesis, we establish that there is a value r∗ which depends on k and p but not on m or n such that if m/n > r∗, then with high probability F_k(n, m) is not p-satisfiable, while if m/n < r∗(1 − δ_k), then with high probability Fk(n, m) is p-satisfiable. Here δ_k → 0 exponentially fast in k. We also give evidence for the notion that any polynomial-time algorithm will not be able to find a p-satisfying assignment of F_k(n, m) with high probability whenever m/n is greater than a threshold r*' much lower than r∗. Roughly speaking, we show that when m/n is between r*' and r∗, with high probability, the solution set shatters into many exponentially small, linearly separated regions of solutions, rendering it difficult to locate a single solution in polynomial time.