Upper bounds on the satisfiability threshold (Q5958807): Difference between revisions

We present a survey of upper bounds which has been established up to now on the satisfiability threshold of random $k$-SAT formulae. The ideas which led to these bounds and the techniques used to obtain them, are explained. A companion paper in this volume present a survey of the lower bounds.

0 references

zbMATH Keywords

satisfiability

0 references

SAT threshold

0 references

phase transition

0 references

upper bounds

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)

0 references

Lower bounds for random 3-SAT via differential equations

0 references

The scaling window of the 2-SAT transition

0 references

Length of prime implicants and number of solutions of random CNF formulae

0 references

Q3140436

0 references

Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

0 references

Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem

0 references

Q4228436

0 references

Many hard examples for resolution

0 references

Experimental results on the crossover point in random 3-SAT

0 references

Q5687266

0 references

A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

0 references

Q4952608

0 references

On Random 3-sat

0 references

Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

0 references

Sharp thresholds of graph properties, and the $k$-sat problem

0 references

Analysis of Two Simple Heuristics on a Random Instance ofk-sat

0 references

A threshold for unsatisfiability

0 references

A threshold for unsatisfiability

0 references

Bounding the unsatisfiability threshold of random 3-SAT

0 references

Tail bounds for occupancy and the satisfiability threshold conjecture

0 references

Q4375776

0 references

Approximating the unsatisfiability threshold of random formulas (Extended Abstract)

0 references

Approximating the unsatisfiability threshold of random formulas

0 references

Determining computational complexity from characteristic ‘phase transitions’

0 references

Q3723699

0 references

Identifiers

zbMATH Open document ID

0983.68082

0 references

DOI

10.1016/S0304-3975(01)00161-X

0 references

Mathematics Subject Classification ID

68Q25

0 references

zbMATH DE Number

1715852

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5958807

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
+Normal rank
@@ Property / cites work @@
+Lower bounds for random 3-SAT via differential equations
+Normal rank
@@ Property / cites work @@
+The scaling window of the 2-SAT transition
@@ Property / cites work: The scaling window of the 2-SAT transition / rank @@
+Normal rank
@@ Property / cites work @@
+Length of prime implicants and number of solutions of random CNF formulae
+Normal rank
@@ Property / cites work @@
+Q3140436
@@ Property / cites work: Q3140436 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
+Normal rank
@@ Property / cites work @@
+Q4228436
@@ Property / cites work: Q4228436 / rank @@
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Experimental results on the crossover point in random 3-SAT
+Normal rank
@@ Property / cites work @@
+Q5687266
@@ Property / cites work: Q5687266 / rank @@
+Normal rank
@@ Property / cites work @@
+A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
+Normal rank
@@ Property / cites work @@
+Q4952608
@@ Property / cites work: Q4952608 / rank @@
+Normal rank
@@ Property / cites work @@
+On Random 3-sat
@@ Property / cites work: On Random 3-sat / rank @@
+Normal rank
@@ Property / cites work @@
+Results related to threshold phenomena research in satisfiability: Lower bounds
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
+Normal rank
@@ Property / cites work @@
+Sharp thresholds of graph properties, and the $k$-sat problem
+Normal rank
@@ Property / cites work @@
+Analysis of Two Simple Heuristics on a Random Instance ofk-sat
+Normal rank
@@ Property / cites work @@
+A threshold for unsatisfiability
@@ Property / cites work: A threshold for unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold for unsatisfiability
@@ Property / cites work: A threshold for unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Bounding the unsatisfiability threshold of random 3-SAT
+Normal rank
@@ Property / cites work @@
+Tail bounds for occupancy and the satisfiability threshold conjecture
+Normal rank
@@ Property / cites work @@
+Q4375776
@@ Property / cites work: Q4375776 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
+Normal rank
@@ Property / cites work @@
+Approximating the unsatisfiability threshold of random formulas
+Normal rank
@@ Property / cites work @@
+Determining computational complexity from characteristic ‘phase transitions’
+Normal rank
@@ Property / cites work @@
+Q3723699
@@ Property / cites work: Q3723699 / rank @@
+Normal rank