Random 3-SAT: The plot thickens

DOI10.1023/A:1025671026963MaRDI QIDQ1424763zbMATH OpenFDO

Authors Cristian Coarfa, Demetrios D. Demopoulos, Alfonso San Miguel Aguirre, Devika Subramanian, Moshe Y. Vardi

Publication date 15 March 2004

Published in Constraints (Search for Journal in Brave)

zbMATH Keywords

average-case complexity

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2080304
• scientific article; zbMATH DE number 2084701
• scientific article; zbMATH DE number 1445295
• The SAT phase transition
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances

Cited in

(6)

• Phase transitions of EXPSPACE-complete problems: a further step
• Symbolic techniques in satisfiability solving
• On the hierarchical community structure of practical Boolean formulas
• scientific article; zbMATH DE number 2084701 (Why is no real title available?)
• scientific article; zbMATH DE number 2080304 (Why is no real title available?)
• Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth

Describes a project that uses

Uses Software

• CUDD
• CPLEX

This page was built for publication: Random 3-SAT: The plot thickens

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