Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T18:19:25.612Z Has data issue: false hasContentIssue false
  • English
  • Français

On Random 3-sat

Published online by Cambridge University Press:  12 September 2008

A. El Maftouhi  and
W. Fernandez De La Vega
A. El Maftouhi
Affiliation:
Laboratoire de Recherche en Informatique, Universite de paris-Sud, Bât. 490, 91405 Orsay Cedex, France
W. Fernandez De La Vega
Affiliation:
Laboratoire de Recherche en Informatique, Universite de paris-Sud, Bât. 490, 91405 Orsay Cedex, France
Get access Rights & Permissions [Opens in a new window]

Abstract

Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 3 , September 1995 , pp. 189 - 195
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bender, A. (1975) Central and Local Limit Theorems Applied to Asymptotic Enumeration. J. Comb. Theory (A) 15 91–111.CrossRefGoogle Scholar
[2]Bollobás, B. (1985) Random Graphs. Academic Press.Google Scholar
[3]Chao, M. T. and Franco, J. (1986) Probabilistic Analysis of Two Heuristics For the 3-Satisfiability Problem. Siam J. Comput. 15(4).CrossRefGoogle Scholar
[4]Chvátal, V. and Reed, B. (1992) Mick Gets Some (The Odds are on his Side). Proc. 3rd Ann. ACM-SIAM Symp. Discrete Algorithms.CrossRefGoogle Scholar
[5]Broder, A. Z., Frieze, A. M. and Upfal, E. (1993) On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas. In Proc. 4th Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 322–330.Google Scholar
[6]Kamath, A., Motwani, R., Palem, K. and Spirakis, P. Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. Proc. 35th FOCS, pp. 592–603.Google Scholar
[7]Fernandez de la Vega, W. (1992) On Random 2-Sat. Draft.Google Scholar
[8]Frieze, A. and Suen, S. (1992) Analysis of Two Simple Heuristics on a Random Instance of k-Sat. Submitted.Google Scholar
[9]Goerdt, A. (1992) A threshold for satisfiability. In Mathematical Foundations of Computer Science (Havel, I. M. and Koubek, V., eds.), Prague, Poland.Google Scholar
[10]Larrabee, T. and Tsuji, Y. (1992) Evidence for a Satisfiability Threshold for Random 3CNF Formulas. Technical Report UCSC-CRL-92–42, Univesity of California, Santa Cruz.Google Scholar
[11]Selman, B., Levesque, H. and Mitchell, D. (1992) A New Method for Solving Hard Satisfiability Problems. In AAAI-92, pp. 440–446.Google Scholar