An algorithm for random signed 3-SAT with intervals
Interval-k-SAT (k-iSAT) is a generalization of classical k -SAT where the variables can take values in [0,1] [ 0 , 1 ] (instead of {0,1} { 0 , 1 } ) and the literals are of the form x?I x ? I , for intervals I?[0,1] I ? [ 0 , 1 ] . It falls within the class of signed satisfiability problems. 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 m / n ? 2.3 , with high probability, our algorithm succeeds in finding an assignment of values to the variables satisfying the formula.
signed satisfiability random constraint satisfaction problems