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

DOI10.1007/BF01531028MaRDI QIDQ1353993zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

set partitioningprobability modelsBoolean 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) Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 4080977
• New algorithms for exact satisfiability
• scientific article; zbMATH DE number 4060775
• Polynomial-average-time satisfiability problems
• Algorithms for four variants of the exact satisfiability problem

Cites work

• scientific article; zbMATH DE number 3643033 (Why is no real title available?)
• scientific article; zbMATH DE number 4060775 (Why is no real title available?)
• scientific article; zbMATH DE number 4080977 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1354158 (Why is no real title available?)
• scientific article; zbMATH DE number 3803174 (Why is no real title available?)
• An Analysis of Backtracking with Search Rearrangement
• An Average Time Analysis of Backtracking
• Asymptotic Methods in Enumeration
• Average time analyses of simplified Davis-Putnam procedures
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• The Pure Literal Rule and Polynomial Average Time

Cited in

(6)

• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• scientific article; zbMATH DE number 4080977 (Why is no real title available?)
• The scientific works of Rainer Kemp (1949--2004)
• scientific article; zbMATH DE number 4060775 (Why is no real title available?)
• 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)