Hello everyone,
My name is Damien Desfontaines, and I'm currently following a Theoretical
Computer Science Major at the École Normale Supérieure in Paris, which is one of
the most selective universities in France.
I am fairly interested in working for SymPy during the Google Summer of Code
program ; and I was looking on the website how I could use my theoretical
background to contribute in an efficient and useful way to this project. Being
really interested in formal logic, I was thinking that I may look at the Logic
module already implemented in SymPy.
So, apparently it contains the bare minimum to play around with boolean
formulas. There is also a SAT-solver, using - tell me if I am wrong - DPLL's
algorithm. So, it makes me think of several suggestions :
- Improving the SAT-solver algorithm. Many research has been done since DPLL,
and some solvers like MiniSAT are much more efficient [1].
- Implementing variants of this algorithm, for particular cases (one may want to
solve a 3-SAT instance for example, and others algorithms exists for those
particular cases - the randomized Schöning's algorithm, for example).
Variants include 2-SAT, 3-SAT, Horn-satisfiability,
XOR-satisfiability, etc [2].
- Implementing a Max-SAT-solver, and so being able to tell the maximum number of
clauses for which there exists an assignment satisfying all of them, in a set
of given clauses. Variants of this algorithm exist too, Max-{2,3}-SAT for
example. [3]
- Implementing heuristic methods, to deal with large inputs.
I would be glad to work on some of those ideas. What do you think is more useful
? I would like to have a research-oriented attitude, implementing and comparing
different algorithms doing the same task to come with the best solution
possible. So, it may be a little optimistic to apply for all of these at the
same time...
Damien Desfontaines
[1]
https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT
http://minisat.se/
[2]
https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Complexity_and_restricted_versions
[3] https://en.wikipedia.org/wiki/Maximum_satisfiability_problem
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
