You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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

Article type: Research Article

Authors: Kutzkov, Konstantin

Affiliations: Naroden geroy 6, 1618 Sofia, Bulgaria. E-mail: [email protected]

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

DOI: 10.3233/SAT190007

Journal: Journal on Satisfiability, Boolean Modeling and Computation, vol. 1, no. 3-4, pp. 143-145, 2006

Received 1 January 2007
|
Revision received 1 March 2007
|
Published: 1 March 2007
Get PDF open access

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.

Show less