Complete on average Boolean satisfiability

DOI10.1006/JCOM.2002.0649MaRDI QIDQ1872642zbMATH OpenOpenAlexFDO

Authors Jie Wang

Publication date 14 May 2003

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.2002.0649

zbMATH Keywords

CNF formulassatisfiabilityaverage NP-completenessdistributional Booleandistributional tilingdynamic binary coding schemerandomized reductions.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• CNF-Satisfiability Test by Counting and Polynomial Average Time
• On Average Case Complexity of SAT for Symmetric Distribution
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Publication:4484662
• scientific article; zbMATH DE number 1444322

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• scientific article; zbMATH DE number 1113991 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Average Case Complete Problems
• Average case completeness
• Distributional Word Problem for Groups
• Many hard examples for resolution
• On the theory of average case complexity
• Probabilistic performance of a heurisic for the satisfiability problem
• Randomizing Reductions of Search Problems

Cited in

(1)

• Collapsing and separating completeness notions under average-case and worst-case hypotheses

This page was built for publication: Complete on average Boolean satisfiability

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