An algorithm for random signed 3-SAT with intervals

DOI10.1016/J.TCS.2013.10.020MaRDI QIDQ2637342zbMATH OpenOpenAlexFDO

Authors Kathrin Ballerstein, Dirk Oliver Theis

Publication date 11 February 2014

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

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

zbMATH Keywords

random constraint satisfaction problemssigned satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Analysis of algorithms (68W40) Logic in computer science (03B70)

Abstract: In signed k-SAT problems, one fixes a set M and a set $mathcalS$ 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 "$xinS$", where $SinmathcalS$, and x is one of n variables. For Interval-SAT (iSAT), M is an ordered set and $mathcalS$ 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/nle2.3$, with high probability, our algorithm succeeds in finding an assignment of values to the variables satisfying the formula.

Recommendations

• A Better Algorithm for Random k-SAT
• A better algorithm for random \(k\)-SAT
• A randomized algorithm for 3-SAT
• A probabilistic algorithm for k-SAT based on limited local search and restart
• Theory and Applications of Satisfiability Testing

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 512980 (Why is no real title available?)
• scientific article; zbMATH DE number 2084702 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1775484 (Why is no real title available?)
• scientific article; zbMATH DE number 1405442 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• A better algorithm for random \(k\)-SAT
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A threshold for unsatisfiability
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Differential equations for random processes and random graphs
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Lower bounds for random 3-SAT via differential equations
• Models and thresholds for random constraint satisfaction problems
• Models for Random Constraint Satisfaction Problems
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probability and random processes.
• Random Intervals
• Random interval graphs
• Regular-SAT: A many-valued approach to solving combinatorial problems
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Sharp thresholds of graph properties, and the $k$-sat problem
• The Helly property and satisfiability of Boolean formulas defined on set families
• The SAT problem of signed CNF formulas
• The SAT-UNSAT transition for random constraint satisfaction problems
• The probabilistic analysis of a greedy satisfiability algorithm
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

Cited in

(1)

• A first polynomial non-clausal class in many-valued logic

This page was built for publication: An algorithm for random signed 3-SAT with intervals

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