Jump to ContentJump to Main Navigation
Computational Complexity and Statistical Physics$
Users without a subscription are not able to see the full content.

Allon Percus, Gabriel Istrate, and Cristopher Moore

Print publication date: 2005

Print ISBN-13: 9780195177374

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195177374.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 17 October 2021

The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements

The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements

Chapter 7 The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements
Computational Complexity and Statistical Physics

Lefteris M. Kirousis

Lefteris M. Stamatiou

Oxford University Press

One of the most challenging problems in probability and complexity theory is to establish and determine the satisfiability threshold, or phase transition, for random 3-SAT instances: Boolean formulas consisting of clauses with exactly k literals. As the previous part of the volume has explored, empirical observations suggest that there exists a critical ratio of the number of clauses to the number of variables, such that almost all randomly generated formulas with a higher ratio are unsatisfiable while almost all randomly generated formulas with a lower ratio are satisfiable. The statement that such a crossover point really exists is called the satisfiability threshold conjecture. Experiments hint at such a direction, but as far as theoretical work is concerned, progress has been difficult. In an important advance, Friedgut [177] showed that the phase transition is a sharp one, though without proving that it takes place at a “fixed” ratio for large formulas. Otherwise, rigorous proofs have focused on providing successively better upper and lower bounds for the value of the (conjectured) threshold. In this chapter, our goal is to review the series of improvements of upper bounds for 3-SAT and the techniques leading to these. We give only a passing reference to the improvements of the lower bounds as they rely on significantly different techniques, one of which is discussed in the next chapter. Let ϕ be a random k-SAT formula constructed by selecting, uniformly and with replacement, ra clauses from the set of all possible clauses with k literals (no variable repetitions allowed within a clause) over n variables. It has been experimentally observed that as the numbers m, n of variables and clauses tend to infinity while the ratio or clause density m/n is fixed to a constant a, the property of satisfiability exhibits a phase transition. For the case of 3-SAT, when a is greater than a number that has been experimentally determined to be approximately α < 4.27, then almost all random 3-SAT formulas are unsatisfiable; that is, the fraction of unsatisfiable formulas tends to 1.

Keywords:   backtracking, control parameter, differential equations, first moment method, g-binomial, harmonic mean formula, method of local maxima, occupancy bounds, partition function, replica method

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .