ПОЛИНОМИАЛЬНАЯ ЭКВИВАЛЕНТНОСТЬ ЗАДАЧ ИЗОМОРФИЗМ ПРЕДИКАТНЫХ ФОРМУЛ И ИЗОМОРФИЗМ ГРАФОВ

Research output

Abstract

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 contributionPolynomial equivalence of the problems predicate formulas isomorphism and graph isomorphism
Original languageRussian
Pages (from-to)430–439
JournalВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Volume6 (64)
Issue number3
Publication statusPublished - May 2019

Scopus subject areas

  • Mathematics(all)
  • Computer Science(all)

Fingerprint Dive into the research topics of 'ПОЛИНОМИАЛЬНАЯ ЭКВИВАЛЕНТНОСТЬ ЗАДАЧ ИЗОМОРФИЗМ ПРЕДИКАТНЫХ ФОРМУЛ И ИЗОМОРФИЗМ ГРАФОВ'. Together they form a unique fingerprint.

Cite this