1. The Feasibility of Solving the Satisfiability Problem Using Various Machine Learning Approaches.
- Author
-
Lan Zhang, Lei Hu, and Lina Yu
- Subjects
- *
DEEP learning , *MACHINE learning , *PROBLEM solving , *MODAL logic , *PROPOSITION (Logic) , *CLASSIFICATION algorithms - Abstract
In this paper, we propose a novel approach to solving theorem proving problems without relying on any deduction method. We transform logical formulas into numbers, vectors and matrices, and feed the corresponding data into various machine learning algorithms to predict their satisfiability. Here, we introduce ProverX, a novel theorem prover that utilizes various binary classification algorithms, ranging from traditional machine learning to deep learning, to tackle the satisfiability (SAT) problem of propositional logic. Empirical experiments were conducted to evaluate the performance of ProverX using datasets we generated. ProverX achieved accuracy rates ranging from 81.8% to 98.7%, demonstrating a remarkable speedup of almost 180 times compared to CTL-RP, a highly efficient prover. These results demonstrate the feasibility of replacing deduction with learning in theorem proving, opening promising avenues for further exploration in more complex logics, e.g., Modal Logic, Coalition Logic, Propositional Linear-Time Temporal Logic, Computation Tree Logic, etc., provided that their resolution methods exist. We also present a detailed analysis of the best-performing machine learning approaches for this task and introduce a new algorithm, IPDA, which has the potential to further enhance performance. [ABSTRACT FROM AUTHOR]
- Published
- 2024