Related Experiment Video
Updated: May 10, 2026

Using Eye Movements Recorded in the Visual World Paradigm to Explore the Online Processing of Spoken Language
Published on: October 13, 2018
Witness of unsatisfiability for a random 3-satisfiability formula
Lu-Lu Wu1, Hai-Jun Zhou, Mikko Alava
1State Key Laboratory for Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
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.
Related Concept Videos
Constraints and Statical Determinacy
Second Uniqueness Theorem
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...
Fundamental Theorem of Algebra
Rationalizing Substitutions
Statically Indeterminate Problem Solving
Gaussian Elimination: Problem Solving
