### A Note on the Use of Independent Sets for the k-SAT Problem

#### Abstract

An independent set of variables is one in which no two variables occur in the same clause in a given k-SAT instance. Recently, independent sets have obtained more attention. Due to a simple observation we prove that a k-SAT instance over n variables with independent set of size i can be solved in time O(φ_{2(k−1)} (n − i)) where φ_{k (n)} denotes an upper bound on the complexity of solving k-SAT over n variables

#### Keywords

k-SAT problem, upper bounds, independent sets of variables

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.