Abstract
The Graph Isomorphism (GI) Class is the class of all the problems equivalent to the Graph Isomorphism problem, that is not known to be solvable in polynomial time nor to be NP-complete. GI thus is a very interesting complexity class that may be in NP-intermediate. In this work we focus on the CNF Syntactic Formula Isomorphism (CSFI) problem, that has been proved to be GI-complete, and we present a formal approach to the definition of “trivial non-isomorphic” instances and an algorithm to generate “non-trivial” instances. The applications of such generator are twofold: on the one side we can use it to compare deterministic algorithms, and on the other side, following recent approaches for NP-complete problems such as SAT and TSP, we can also use the generated instances to train neural networks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agrawal, M., Thierauf, T.: The Boolean isomorphism problem. In: Proceedings of 37th Conference on Foundations of Computer Science (FOCS), pp. 422–430. IEEE (1996)
Agrawal, M., Thierauf, T.: The formula isomorphism problem. SIAM J. Comput. 30(3), 990–1009 (2000)
Ausiello, G., Cristiano, F., Fantozzi, P., Laura, L.: Syntactic isomorphism of CNF Boolean formulas is graph isomorphism complete. In: Cordasco, G., Gargano, L., Rescigno, A.A. (eds.), Proceedings of the 21st Italian Conference on Theoretical Computer Science, Ischia, Italy, 14–16 September 2020, CEUR Workshop Proceedings, vol. 2756, pp. 190–201 (2020). CEUR-WS.org
Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. ACM Press, New York (2016)
Benedetto, L., Fantozzi, P., Laura, L.: Complexity-based partitioning of CSFI problem instances with transformers (2021)
McKay, B.D., et al.: Practical graph isomorphism (1981)
McKay, B.D., Piperno, A.: Practical graph isomorphism. II. J. Symbol. Comput. 60, 94–112 (2014)
Prates, M., Avelar, P.H.C., Lemos, H., Lamb, L.C., Vardi, M.Y.: Learning to solve NP-complete problems: a graph neural network for decision TSP. In: AAAI, vol. 33, no. 01, pp. 4731–4738 (2019)
Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., Dill, D.L.: Learning a SAT solver from single-bit supervision, February 2018
Thierauf, T.: The Computational Complexity of Equivalence and Isomorphism Problems. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45303-2
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fantozzi, P., Laura, L., Nanni, U., Villa, A. (2022). Non-isomorphic CNF Generation. In: Matsui, K., Omatu, S., Yigitcanlar, T., González, S.R. (eds) Distributed Computing and Artificial Intelligence, Volume 1: 18th International Conference. DCAI 2021. Lecture Notes in Networks and Systems, vol 327. Springer, Cham. https://doi.org/10.1007/978-3-030-86261-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-86261-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86260-2
Online ISBN: 978-3-030-86261-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)