Java Implementation Of A SAT Solver (SATe).pdf

- SATe is a Java SAT solver that takes boolean expressions in Conjunctive Normal Form (CNF) as input and outputs whether the expression is satisfiable or not. If satisfiable, it generates an assignment that satisfies the expression.
- Approach: SATe first negates the CNF expression to Disjunctive Normal Form (DNF) and tries to find an assignment that causes the complemented expression to fail, thus satisfying the original expression. It does this by:
- Splitting the problem into sub-problems based on assigning true or false to a selected literal.
- Performing four simplifications on each sub-problem: handling single literal clauses, simplifying using literal usage, identifying 'fixed variable pairs' (FVPs) or 'contrarian pairs' in two-literal clauses, and managing conflicting assignments.
- Performance: SATe's performance was compared to MiniSat on the SATLIB test suite. While MiniSat performed better, SATe showed surprisingly good performance given it's implemented in Java. Java's interpreted nature and run-time optimization (JIT) contribute to its slower performance compared to C++.
- Testing: Timing results were generated by running the Java application separately for each expression in the test set. Figures 1-4 show the performance of SATe and MiniSat on satisfiable and non-satisfiable expressions with 150 literals, with and without amortizing class loading and JIT optimization costs.