Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT (Q1777400): Difference between revisions

Latest revision as of 11:28, 10 June 2024

scientific article

Language	Label	Description	Also known as
English	Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT	scientific article

Statements

instance of

scholarly article

0 references

title

Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT (English)

0 references

0 references

0 references

Annals of Mathematics and Artificial Intelligence

0 references

publication date

13 May 2005

0 references

full work available at URL

https://arxiv.org/abs/cond-mat/0206242

0 references

zbMATH Keywords

restart

0 references

satisfiability

0 references

DPLL

0 references

large deviations

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Lower bounds for random 3-SAT via differential equations

0 references

A sharp threshold in proof complexity

0 references

Rigorous results for random ($2+p)$-SAT

0 references

Q4542576

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

Many hard examples for resolution

0 references

Q4473023

0 references

A machine program for theorem-proving

0 references

Q5687266

0 references

Q4952608

0 references

Statistical mechanics methods and phase transitions in optimization problems

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

Easy problems are sometimes hard

0 references

Q2703800

0 references

Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

0 references

Q4375757

0 references

The hardest constraint problems: A double phase transition

0 references

Q4411392

0 references

Critical Behavior in the Satisfiability of Random Boolean Expressions

0 references

Determining computational complexity from characteristic ‘phase transitions’

0 references

Q4704799

0 references

Critical behavior in the computational cost of satisfiability testing

0 references

Identifiers

zbMATH Open document ID

1100.68576

0 references

DOI

10.1007/s10472-005-0426-4

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1777400

@@ Property / author @@
-Remi Monasson
@@ Property / author: Remi Monasson / rank @@
-Normal rank
@@ Property / author @@
+Remi Monasson
@@ Property / author: Remi Monasson / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3005320095
@@ Property / OpenAlex ID: W3005320095 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+cond-mat/0206242
@@ Property / arXiv ID: cond-mat/0206242 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for random 3-SAT via differential equations
+Normal rank
@@ Property / cites work @@
+A sharp threshold in proof complexity
@@ Property / cites work: A sharp threshold in proof complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Rigorous results for random (\(2+p)\)-SAT
@@ Property / cites work: Rigorous results for random (\(2+p)\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Q4542576
@@ Property / cites work: Q4542576 / 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 @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4473023
@@ Property / cites work: Q4473023 / 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 @@
+Q5687266
@@ Property / cites work: Q5687266 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4952608
@@ Property / cites work: Q4952608 / rank @@
+Normal rank
@@ Property / cites work @@
+Statistical mechanics methods and phase transitions in optimization problems
+Normal rank
@@ Property / cites work @@
+Results related to threshold phenomena research in satisfiability: Lower bounds
+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 @@
+Easy problems are sometimes hard
@@ Property / cites work: Easy problems are sometimes hard / rank @@
+Normal rank
@@ Property / cites work @@
+Q2703800
@@ Property / cites work: Q2703800 / rank @@
+Normal rank
@@ Property / cites work @@
+Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
+Normal rank
@@ Property / cites work @@
+Q4375757
@@ Property / cites work: Q4375757 / rank @@
+Normal rank
@@ Property / cites work @@
+The hardest constraint problems: A double phase transition
+Normal rank
@@ Property / cites work @@
+Q4411392
@@ Property / cites work: Q4411392 / rank @@
+Normal rank
@@ Property / cites work @@
+Critical Behavior in the Satisfiability of Random Boolean Expressions
+Normal rank
@@ Property / cites work @@
+Determining computational complexity from characteristic ‘phase transitions’
+Normal rank
@@ Property / cites work @@
+Q4704799
@@ Property / cites work: Q4704799 / rank @@
+Normal rank
@@ Property / cites work @@
+Critical behavior in the computational cost of satisfiability testing
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1777400