Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism

DOI10.1134/S1063454119030105zbMath1480.68010OpenAlexW2971393100MaRDI QIDQ2282762

Nikolaĭ Nikolaevich Kosovskiĭ, Tat'yana Matveevna Kosovskaya

Publication date: 19 December 2019

Published in: Vestnik St. Petersburg University. Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1063454119030105

zbMATH Keywords

graph isomorphismGI-completenesspredicate formulas isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Estimating the number of steps that it takes to solve some problems of pattern recognition which admit logical description
• Graph isomorphism problem
• The NP-completeness column

This page was built for publication: Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism