Some notes on random satisfiability

DOI10.1007/3-540-45322-9_8MaRDI QIDQ4739606zbMATH OpenFDO

Authors Gregory B. Sorkin

Publication date 6 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2264/22640117.htm

zbMATH Keywords

2-SAT3-SATaverage-case analysiscomplexitydifferential equation methodphase transitionrandomized analysis of algorithmssatisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Theory and Applications of Satisfiability Testing
• The power of choice for random satisfiability
• On the random satisfiable process
• Random 2-SAT and unsatisfiability
• On the complexity of random satisfiability problems with planted solutions
• A remark on random 2-SAT
• scientific article; zbMATH DE number 2151254
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• On the maximum satisfiability of random formulas
• On the complexity of random satisfiability problems with planted solutions (extended abstract)

Cited in

(29)

• Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
• Experimental results on the crossover point in random 3-SAT
• Implicates and prime implicates in random 3-SAT
• Critical behavior in the computational cost of satisfiability testing
• Phase transitions of PP-complete satisfiability problems. (Abstract)
• Probabilistic analysis of satisfiability algorithms
• Why almost all satisfiable k-CNF formulas are easy
• The probabilistic analysis of a greedy satisfiability algorithm
• scientific article; zbMATH DE number 2079360 (Why is no real title available?)
• Random 3-SAT: The plot thickens
• Random 3-SAT and BDDs: The plot thickens further
• Random MAX SAT, random MAX CUT, and their phase transitions
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• The phase transition in exact cover
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Principles and Practice of Constraint Programming – CP 2004
• Lower bounds for random 3-SAT via differential equations
• An improved generator for 3-CNF formulas
• Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability
• On threshold properties of k-SAT: An additive viewpoint
• Density condensation of Boolean formulas
• Regular random \(k\)-SAT: Properties of balanced formulas
• An efficient approach to solving random \(k\)-SAT problems
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas

This page was built for publication: Some notes on random satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4739606)