Exact satisfiability, a natural extension of set partition, and its average case behavior
DOI10.1007/BF01531028zbMATH Open0865.03030OpenAlexW2037639986MaRDI QIDQ1353993FDOQ1353993
Authors: John W. Rosenthal, Ewald Speckenmeyer, Rainer Kemp 
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
Recommendations
set partitioningprobability modelsBoolean formulaaverage time complexityconjunctive normal formbacktracking strategyconstant degree modelconstant density modelexact satisfiability problemlow degree polynomial time
Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Asymptotic Methods in Enumeration
- Title not available (Why is that?)
- An Analysis of Backtracking with Search Rearrangement
- An Average Time Analysis of Backtracking
- Average time analyses of simplified Davis-Putnam procedures
- Title not available (Why is that?)
- The Pure Literal Rule and Polynomial Average Time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (6)
- An algorithm for exact satisfiability analysed with the number of clauses as parameter
- Title not available (Why is that?)
- The scientific works of Rainer Kemp (1949--2004)
- Title not available (Why is that?)
- Inapproximability results for set splitting and satisfiability problems with no mixed clauses
- On domain-partitioning induction criteria: worst-case bounds for the worst-case based
This page was built for publication: Exact satisfiability, a natural extension of set partition, and its average case behavior
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1353993)
