A randomized algorithm for 3-SAT

DOI10.1007/S11786-010-0036-3MaRDI QIDQ626900zbMATH OpenOpenAlexFDO

Authors Subhas Kumar Ghosh, Janardan Misra

Publication date 19 February 2011

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.1849

zbMATH Keywords

analysis of algorithmsBoolean satisfiabilityexponential time algorithmrandomized algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Abstract: In this work we propose and analyze a simple randomized algorithm to find a satisfiable assignment for a Boolean formula in conjunctive normal form (CNF) having at most 3 literals in every clause. Given a k-CNF formula phi on n variables, and alpha in{0,1}^n that satisfies phi, a clause of phi is critical if exactly one literal of that clause is satisfied under assignment alpha. Paturi et. al. (Chicago Journal of Theoretical Computer Science 1999) proposed a simple randomized algorithm (PPZ) for k-SAT for which success probability increases with the number of critical clauses (with respect to a fixed satisfiable solution of the input formula). Here, we first describe another simple randomized algorithm DEL which performs better if the number of critical clauses are less (with respect to a fixed satisfiable solution of the input formula). Subsequently, we combine these two simple algorithms such that the success probability of the combined algorithm is maximum of the success probabilities of PPZ and DEL on every input instance. We show that when the average number of clauses per variable that appear as unique true literal in one or more critical clauses in phi is between 1 and 1.9317, combined algorithm performs better than the PPZ algorithm.

Recommendations

• Randomized algorithms for 3-SAT
• A combinatorial analysis for the critical clause tree
• A probabilistic algorithm for k-SAT based on limited local search and restart
• The probabilistic analysis of a greedy satisfiability algorithm
• A Better Algorithm for Random k-SAT

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A machine program for theorem-proving
• A necessary condition on minimal cube numberings
• A probabilistic algorithm for k-SAT based on limited local search and restart
• An improved deterministic local search algorithm for 3-SAT
• An improved exponential-time algorithm for k -SAT
• scientific article; zbMATH DE number 3747068 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• New methods for 3-SAT decision and worst-case analysis
• Randomized algorithms for 3-SAT
• Solving satisfiability in less than \(2^ n\) steps
• The complexity of theorem-proving procedures
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Theory and Applications of Satisfiability Testing

Cited in

(6)

• A combinatorial analysis for the critical clause tree
• An algorithm for random signed 3-SAT with intervals
• Improving PPSZ for 3-SAT using critical variables
• Hard satisfiable 3-SAT instances via autocorrelation
• AI 2003: Advances in Artificial Intelligence
• Computer Science Logic

This page was built for publication: A randomized algorithm for 3-SAT

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