arXiv preprint ·
Efficient NPN Classification for Large Functions using Graph Neural Network
- Published
- Source
- arXiv preprint, posted before peer review
- DOI
- 10.1145/3831252.3834266
- Original
- Read it at arXiv
- Topics
Abstract
Two Boolean functions are considered NPN equivalent if one can be transformed into the other by negating inputs, permuting inputs, or negating the output. Efficient NPN classification is valuable in fields such as logic synthesis, quantum computing, and information theory. However, exact NPN classification demands exhaustive enumeration of all possible input permutations and negations. Its complexity grows exponentially, making it impractical for larger functions with more inputs. In this paper, we introduce the first learning-based formulation for NPN classification by recasting it as NPN action prediction. Our method represents Boolean functions as AND-Inverter Graphs (AIGs) and applies a bidirectional heterogeneous graph neural network to predict input negations, output negation, and input permutations. To mitigate the non-canonicity of logic networks, we further introduce graph rewriting techniques that reduce structural ambiguity and recover useful symmetries before prediction. Experimental results show that NPN action prediction is learnable, that the resulting canonicalization quality improves over heuristic baselines, and that on practical benchmarks our method approaches exact methods on tractable cases while scaling to functions with up to 16 inputs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
CIRCE Divines LLM Task Complexity from Constraint Structure
Few Trials, Many Metrics: Beta Mixtures for Low-Budget AI Evaluation
Verifying Text-to-SQL Queries under Changing Business Semantics
Threat Modeling Intimate Partner Abuse in Agentic Systems
QUAL: Quantile Alignment Improves Zero-Shot Time-Series Foundation Models
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.