Generalized satisfiability problems: Minimal elements and phase transitions.

DOI10.1016/S0304-3975(02)00890-3zbMath1051.68075OpenAlexW2033086906MaRDI QIDQ1401338

Hervé Daudé, Nadia Creignou

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00890-3

zbMATH Keywords

SatisfiabilityPhase transitionMinimal elementsRandom structuresThreshold phenomenon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (13)

A sharp threshold for a random constraint satisfaction problem ⋮ An algorithm for random signed 3-SAT with intervals ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ The SAT-UNSAT transition for random constraint satisfaction problems ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ When does the giant component bring unsatisfiability? ⋮ A sharp threshold for the renameable-Horn and the \(q\)-Horn properties ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Threshold properties of random Boolean constraint satisfaction problems

Cites Work

• A threshold for unsatisfiability
• Random 2-SAT and unsatisfiability
• Satisfiability threshold for random XOR-CNF formulas
• Generating hard satisfiability problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The scaling window of the 2-SAT transition
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds of graph properties, and the $k$-sat problem
• The complexity of satisfiability problems
• Statistical mechanics methods and phase transitions in optimization problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generalized satisfiability problems: Minimal elements and phase transitions.