Complexity-based partitioning of CSFI problem instances with Transformers
This work addresses a domain-specific challenge in computational logic by providing an incremental method to optimize resource allocation for solving CSFI instances.
The paper tackles the problem of partitioning instances of the Conjunctive Normal Form Syntactic Formula Isomorphism (CSFI) problem by complexity, using a two-step Transformer-based approach to identify instances solvable with fewer resources, and reports promising results on a pseudo-randomly generated dataset.
In this paper, we propose a two-steps approach to partition instances of the Conjunctive Normal Form (CNF) Syntactic Formula Isomorphism problem (CSFI) into groups of different complexity. First, we build a model, based on the Transformer architecture, that attempts to solve instances of the CSFI problem. Then, we leverage the errors of such model and train a second Transformer-based model to partition the problem instances into groups of different complexity, thus detecting the ones that can be solved without using too expensive resources. We evaluate the proposed approach on a pseudo-randomly generated dataset and obtain promising results. Finally, we discuss the possibility of extending this approach to other problems based on the same type of textual representation.