Javascript must be enabled for the correct page display

An algebraic approach to the Boolean Satisfiability Problem

Bakker, P.W. (2016) An algebraic approach to the Boolean Satisfiability Problem. Master's Thesis / Essay, Mathematics.

[img]
Preview
Text
Thesis.pdf - Published Version

Download (996kB) | Preview
[img] Text
Toestemming.pdf - Other
Restricted to Backend only

Download (288kB)

Abstract

This thesis combines the field of Algebra and the field of Logic by investigating the relation between an algebraic and a propositional approach to the Boolean Satisfiability Problem (SAT). The algebraic variant is obtained by representing propositional formulas by polynomials in F2[x1, ..., xn]. We consider the common zeros of the ideal hf(x1, ..., xn), x2 1 +x1, ..., x2 n + xni in order to determine whether f is satisfiable. To develop an algorithm which enables us to analyse and solve the problem, several algebraic concepts are considered. The most important results are obtained from concepts related to Gr¨obner bases. Finally, some algebraic algorithms are obtained which solve SAT. Using the computer algebra system Maple, we get some results on the running time of the algorithms.

Item Type: Thesis (Master's Thesis / Essay)
Degree programme: Mathematics
Thesis type: Master's Thesis / Essay
Language: English
Date Deposited: 15 Feb 2018 08:24
Last Modified: 15 Feb 2018 08:24
URI: http://fse.studenttheses.ub.rug.nl/id/eprint/14349

Actions (login required)

View Item View Item