A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses

DOI10.1016/S1567-8326(00)00002-3zbMath0970.68072MaRDI QIDQ5931554

Paul E. Dunne, Trevor J. M. Bench-Capon

Publication date: 10 October 2001

Published in: The Journal of Logic and Algebraic Programming (Search for Journal in Brave)

zbMATH Keywords

Horn clausessatisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Minimal hypotheses: extension-based semantics to argumentation ⋮ The complexity landscape of claim-augmented argumentation frameworks ⋮ On the preferred extensions of argumentation frameworks: bijections with naive sets ⋮ Combinatorial Problems for Horn Clauses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Generating hard satisfiability problems
• Experimental results on the crossover point in random 3-SAT
• Implicates and prime implicates in random 3-SAT
• Many hard examples for resolution
• Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
• Every monotone graph property has a sharp threshold
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat

This page was built for publication: A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses