Metraipolis › archive › dc_8dce40a047f6
Efficient NPN Classification for Large Functions using Graph Neural Network — arXiv:2611.00339
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.00339
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T10:21:43.754Z
- SHA-256 of the archived text
e92167b6e6578ae30f69f089882c3073af906d1be78cfaba22d8cc563b5a74ff- Stable URL of this page
https://metraipolis.com/documento/dc_8dce40a047f6
How to cite
Efficient NPN Classification for Large Functions using Graph Neural Network — arXiv:2611.00339 — arXiv (en), https://arxiv.org/abs/2611.00339 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8dce40a047f6 (Metraipolis archive dc_8dce40a047f6, sha256 e92167b6e6578ae30f69f089882c3073af906d1be78cfaba22d8cc563b5a74ff)
BibTeX
@misc{dc8dce40a047f6,
title = {Efficient NPN Classification for Large Functions using Graph Neural Network — arXiv:2611.00339},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.00339},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8dce40a047f6; sha256 e92167b6e6578ae30f69f089882c3073af906d1be78cfaba22d8cc563b5a74ff},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00339. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno). Categorie arXiv: Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2611.00339 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T10:19:49.751Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).