title: Witness of unsatisfiability for a random 3-satisfiability formula.
abstract: The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density α exceeds a critical value α(s)≈4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density α>19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when α scales at least linearly with the variable number N, but the focused local search algorithm works for clause density α>cN(b) with b≈0.59 and prefactor c≈8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.
authors.affiliation: State Key Laboratory for Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
authors.forename: Lu-Lu
authors.initials: LL
authors.lastname: Wu
authors.forename: Hai-Jun
authors.initials: HJ
authors.lastname: Zhou
authors.forename: Mikko
authors.initials: M
authors.lastname: Alava
authors.forename: Erik
authors.initials: E
authors.lastname: Aurell
authors.forename: Pekka
authors.initials: P
authors.lastname: Orponen
mesh_terms: D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D015233:Models, Statistical; D018401:Sample Size