Полиномиальная эквивалентность задач изоморфизм предикатных формул и изоморфизм графов

Tatiana M. Kosovskaya; Nikolay N. Kosovskii

Authors

Tatiana M. Kosovskaya
Nikolay N. Kosovskii

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.

Downloads

Download data is not yet available.

References

1. Babai L. Graph Isomorphism in Quasipolynomial Time (Version 2.1 Unfinished revision of Version 2 posted on arXivMay 23, 2017). URL: http://people.cs.uchicago.edu/˜laci/17groups/version2.1.pdf (дата обращения: 21.03.19).

2. Земляченко В.Н., Корнеенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов // Записки научных семинаров ЛОМИ. 1982. Т. 118. С. 83-158.

3. Arvind V., Toran J. Isomorphism testing: Perspectives and open problems // Bulletin of the European Association for Theoretical Computer Science. 2005. Vol. 86. P. 66-84.

4. Johnson D. S. The NP-Completeness Column // ACM Transactions on Algorithms. 2005. Vol. 1. P. 160-176.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М.: Мир, 1982.

6. Kosovskaya T. Predicate Calculus as a Tool for AI Problems Solution: Algorithms and Their Complexity // In: Intelligent System. Open access peer-reviewed chapter. Edited by Chatchawal Wongchoosuk Kasetsart University. URL: https://www.intechopen.com/books/intelligent-system/predicatecalculus-as-a-tool-for-ai-problems-solution-algorithms-and-their-complexity (дата обращения: 21.03.19).

7. Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестник С-Петерб. ун-та. Сер. 1. Математика. Механика. Астрономия. 2007. Вып. 4. С. 82-90.

8. Косовская Т.М. Некоторые задачи искусственного интеллекта, допускающие формализацию на языке исчисления предикатов, и оценки числа шагов их решения // Труды СПИИРАН, 2010. Вып. 14. С. 58-75.

9. Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестник С-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2008. Вып. 1. С. 64-72.

10. Косовская Т.М. Подход к решению задачи построения многоуровневого описания классов на языке исчисления предикатов // Труды СПИИРАН. 2014. №3(34). С. 204-217.

11. Косовская Т.М. Построение многоуровневой базы для уменьшения вычислительной сложности решения задачи конъюнктивный булевский запрос //Материалы конференции ¾Информационные технологии в управлении¿ (ИТУ-2018), 2-4 октября 2018 г., Санкт-Петербург, 2018. С. 33-38.