Research on Abstraction-Based Search Space Partitioning and Solving Satisfiability Problems

Yuexin Huang, Qinzhou Niu () and Yanfang Song
Additional contact information
Yuexin Huang: College of Computer and Engineering, Guilin University of Technology, Guilin 541006, China
Qinzhou Niu: College of Computer and Engineering, Guilin University of Technology, Guilin 541006, China
Yanfang Song: College of Arts, Guilin University of Technology, Guilin 541006, China

Mathematics, 2025, vol. 13, issue 5, 1-25

Abstract: Solving satisfiability problems is central to many areas of computer science, including artificial intelligence and optimization. Efficiently solving satisfiability problems requires exploring vast search spaces, where search space partitioning plays a key role in improving solving efficiency. This paper defines search spaces and their partitioning, focusing on the relationship between partitioning strategies and satisfiability problem solving. By introducing an abstraction method for partitioning the search space—distinct from traditional assignment-based approaches—the paper proposes sequential, parallel, and hybrid solving algorithms. Experimental results show that the hybrid approach, combining abstraction and assignment, significantly accelerates solving in most cases. Furthermore, a unified method for search space partitioning is presented, defining independent and complete partitions. This method offers a new direction for enhancing the efficiency of SAT problem solving and provides a foundation for future research in the field.

Keywords: SAT problem; search space partitioning; abstraction method; hybrid solving algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/5/868/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/5/868/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:5:p:868-:d:1606025

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().