Article citationsMore >>

Harsh Bhasin and Nishant Gupta, (2012), “Randomized algorithm approach for solving PCP”, International Journal on Computer Science and Engineering (IJCSE),Vol. 4, Issue 1, pp. 106-113.

has been cited by the following article:

Article

Genetic Algorithm Based Solution to SAT-3 Problem

1Department of Computer Science, Jamia Hamdard, New Delhi, India


Journal of Computer Sciences and Applications. 2015, Vol. 3 No. 2, 33-39
DOI: 10.12691/jcsa-3-2-3
Copyright © 2015 Science and Education Publishing

Cite this paper:
Umme Aiman, Nausheen Asrar. Genetic Algorithm Based Solution to SAT-3 Problem. Journal of Computer Sciences and Applications. 2015; 3(2):33-39. doi: 10.12691/jcsa-3-2-3.

Correspondence to: Umme  Aiman, Department of Computer Science, Jamia Hamdard, New Delhi, India. Email: aimanraza16@gmail.com

Abstract

SAT-3 is an NP-complete problem for determining whether there exists a solution satisfying a given Boolean formula in the Conjunctive Normal Form, wherein each clause has at most three literals. Existing approaches of this problem take exponential time and are also memory inefficient. The work uses Genetic Algorithms for finding an optimal solution to this problem. The central idea is the intelligent exploitation of a random search used to solve optimization problems. The work explores previous works to direct the search into regions of better performance within the search space, thus reducing the time and space complexity. It thus establishes the ability of Genetic Algorithms for finding optimal solutions from a huge set of solutions. The work has been implemented and analyzed with satisfactory results.

Keywords