An algorithm for random signed 3-SAT with intervals

DOI10.1016/J.TCS.2013.10.020zbMATH Open1285.68210arXiv1105.2525OpenAlexW2963530586MaRDI QIDQ2637342FDOQ2637342

Authors: Kathrin Ballerstein, Dirk Oliver Theis 

Publication date: 11 February 2014

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

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.

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

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

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)

Cites Work

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

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)