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.
Non-isomorphic CNF Generation / Fantozzi, P.; Laura, L.; Nanni, U.; Villa, A.. - 327:(2022), pp. 98-107. (Intervento presentato al convegno 18th International Symposium on Distributed Computing and Artificial Intelligence, DCAI 2021 tenutosi a Salamanca; Spain) [10.1007/978-3-030-86261-9_10].
Non-isomorphic CNF Generation
Fantozzi P.
;Laura L.;Nanni U.;
2022
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
