@article{
    WZAA13,
    author = "Wu, Lu-Lu and Zhou, Hai-Jun and Alava, Mikko and Aurell, Erik and Orponen, Pekka",
    note = "",
    doi = "10.1103/PhysRevE.87.052807",
    responsibleauthor = "Aurell, Erik and Alava, Mikko and Orponen, Pekka",
    language = "eng",
    title = "Witness of unsatisfiability for a random 3-satisfiability formula",
    journal = "Physical Review E",
    issn = "1550-2376",
    number = "5",
    abstract = "The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density $\alpha$ exceeds a critical value $\alpha_s \approx 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 $\alpha > 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 $\alpha$ scales at least linearly with the variable number N, but the focused local search algorithm works for clause density $\alpha > cN^b$ with $b \approx 0.59$ and prefactor $c \approx 8$. The exponent $b$ can be further decreased by enlarging the single parameter $S$ of the focused local search algorithm.",
    month = "May",
    volume = "87",
    unitcode = "T306-99, T312-1",
    juforank = "2",
    il = "yes",
    year = "2013",
    keywords = "",
    flags = "public HIIT",
    kay = "NA",
    impactfactor = "A1",
    pages = "052807"
}