An algorithm for random signed 3-SAT with Intervals

2011/05/12 by Kathrin Ballerstein, Ballerstein, Kathrin, Dirk Oliver Theis +1
Computer Science · Mathematics · #05C80 #68Q87 #68W40 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO #msc:05C80 #msc:68Q87 #msc:68W40

paper · pdf · doi:10.48550/arxiv.1105.2525

30 pages + appendix

arxiv created 2013/08/14 · arxiv updated 2013/08/15

Abstract

In signed k-SAT problems, one fixes a set M and a set \mathcal S of subsets of M, and is given a formula consisting of a disjunction of m clauses, each of which is a conjunction of k literals. Each literal is of the form "x ∈ S", where S ∈ \mathcal S, and x is one of n variables. For Interval-SAT (iSAT), M is an ordered set and \mathcal S the set of intervals in M. We propose an algorithm for 3-iSAT, and analyze it on uniformly random formulas. The algorithm follows the Unit Clause paradigm, enhanced by a (very limited) backtracking option. Using Wormald's ODE method, we prove that, if m/n ≤ 2.3, with high probability, our algorithm succeeds in finding an assignment of values to the variables satisfying the formula.

Related

• On the satisfiability of random regular signed SAT formulas
• On the satisfiability of random 3-SAT formulas with k-wise independent clauses
• The Threshold for Random k-SAT is 2^k ln2 - O(k)
• SARRIGUREN: a polynomial-time complete algorithm for random k-SAT with relatively dense clauses
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52