On Average Case Complexity of SAT for Symmetric Distribution

DOI10.1093/LOGCOM/5.1.71zbMATH Open0989.03039OpenAlexW2001598818MaRDI QIDQ4323003

Abraham Sharell, Johann A. Makowsky

Publication date: 25 June 1996

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/5.1.71

zbMATH Keywords

satisfiability problemresolutionprobabilistic analysis of algorithmsaverage case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Computer Science Logic

Recommendations

• Title not available (Why is that?) 👍 👎
• On the theory of average case complexity 👍 👎
• Average case results for satisfiability algorithms under the random-clause-width model 👍 👎
• On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. 👍 👎
• Average complexity of symmetric Boolean functions 👍 👎
• On the average-case complexity of Boolean functions under binomial distribution on their domains 👍 👎
• On the Average Case Complexity of Some P-complete Problems 👍 👎
• Complexity of Distributions and Average-Case Hardness 👍 👎
• Computer Science Logic 👍 👎

This page was built for publication: On Average Case Complexity of SAT for Symmetric Distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4323003)