A problem of isomorphism checking of two elementary conjunctions of predicate formulas is under consideration. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.
|Translated title of the contribution||Polynomial equivalence of the problems predicate formulas isomorphism and graph isomorphism|
|Journal||ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ|
|Publication status||Published - May 2019|
Scopus subject areas
- Computer Science(all)