Exact satisfiability, a natural extension of set partition, and its average case behavior

DOI10.1007/BF01531028zbMath0865.03030OpenAlexW2037639986MaRDI QIDQ1353993

Ewald Speckenmeyer, Rainer Kemp, John W. Rosenthal

Publication date: 13 May 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01531028

zbMATH Keywords

probability modelsset partitioningBoolean formulaaverage time complexityconjunctive normal formbacktracking strategyconstant degree modelconstant density modelexact satisfiability problemlow degree polynomial time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Related Items (2)

The scientific works of Rainer Kemp (1949--2004) ⋮ An algorithm for exact satisfiability analysed with the number of clauses as parameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average time analyses of simplified Davis-Putnam procedures
• An Analysis of Backtracking with Search Rearrangement
• The Pure Literal Rule and Polynomial Average Time
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• An Average Time Analysis of Backtracking
• Asymptotic Methods in Enumeration

This page was built for publication: Exact satisfiability, a natural extension of set partition, and its average case behavior