Bakker, P.W. (2016) An algebraic approach to the Boolean Satisfiability Problem. Master's Thesis / Essay, Mathematics.
|
Text
Thesis.pdf - Published Version Download (996kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
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: | https://fse.studenttheses.ub.rug.nl/id/eprint/14349 |
Actions (login required)
 |
View Item |