Results related to threshold phenomena research in satisfiability: Lower bounds (Q5958805): Difference between revisions

We present a history of results related to the threshold phenomena which arise in the study of random conjunctive normal form (CNF) formulas. In a companion paper (\textit{D. Achlioptas}, see Zbl 0983.68053) the major ideas used to achieve many of the lower bounds results on the location of the threshold are described in an informal, intuitive manner.

0 references

zbMATH Keywords

satisfiability

0 references

phase transition

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Lower bounds for random 3-SAT via differential equations

0 references

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

0 references

Random constraint satisfaction: A more accurate picture

0 references

Q3140436

0 references

Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

0 references

Q4228436

0 references

The complexity of theorem-proving procedures

0 references

A machine program for theorem-proving

0 references

A Computing Procedure for Quantification Theory

0 references

Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms

0 references

Probabilistic performance of a heurisic for the satisfiability problem

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

Average time analyses of simplified Davis-Putnam procedures

0 references

Phase transitions and the search problem

0 references

Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem''

0 references

Probe Order Backtracking

0 references

A Machine-Oriented Logic Based on the Resolution Principle

0 references

Generating hard satisfiability problems

0 references

Identifiers

zbMATH Open document ID

0983.68081

0 references

DOI

10.1016/S0304-3975(01)00158-X

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5958805

@@ Property / cites work @@
+Lower bounds for random 3-SAT via differential equations
+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 @@
+Random constraint satisfaction: A more accurate picture
+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 @@
+Q4228436
@@ Property / cites work: Q4228436 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+A machine program for theorem-proving
@@ Property / cites work: A machine program for theorem-proving / rank @@
+Normal rank
@@ Property / cites work @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
+Normal rank
@@ Property / cites work @@
+Probabilistic performance of a heurisic for the satisfiability problem
+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 @@
+Average time analyses of simplified Davis-Putnam procedures
+Normal rank
@@ Property / cites work @@
+Phase transitions and the search problem
@@ Property / cites work: Phase transitions and the search problem / rank @@
+Normal rank
@@ Property / cites work @@
+Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem''
+Normal rank
@@ Property / cites work @@
+Probe Order Backtracking
@@ Property / cites work: Probe Order Backtracking / rank @@
+Normal rank
@@ Property / cites work @@
+A Machine-Oriented Logic Based on the Resolution Principle
+Normal rank
@@ Property / cites work @@
+Generating hard satisfiability problems
@@ Property / cites work: Generating hard satisfiability problems / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q126527927
@@ Property / Wikidata QID: Q126527927 / rank @@
+Normal rank