An algorithm for random signed 3-SAT with Intervals

Details An algorithm for random signed 3-SAT with Intervals An algorithm for random signed 3-SAT with Intervals

2011-05-12

arxiv.org/abs/1105.2525v2

Mathematics

Combinatorics

30 pages + appendix

Scientific paper

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 \in S$", where $S \in \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 \le 2.3$, with high probability, our algorithm succeeds in finding an assignment of values to the variables satisfying the formula.

Affiliated with

Also associated with

No associations

Rating

An algorithm for random signed 3-SAT with Intervals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An algorithm for random signed 3-SAT with Intervals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An algorithm for random signed 3-SAT with Intervals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497373