О сложности верификации недетерминированных вероятностных мультиагентных систем

Рассматриваются вероятностные системы взаимодействующих недетерминированных интеллектуальных агентов. Состояниями агентов в таких системах являются вероятностные базы данных (фактов), а их действия управляются вероятностными логическими программами. Кроме того, каналы взаимодействий между агентами также являются вероятностными. Показано, как таким системам за полиномиальное время могут быть сопоставлены моделирующие их конечные Марковские процессы принятия решений. Это позволяет перенести известные результаты о верификации динамических свойств конечных Марковских процессов на вероятностные мультиагентные системы рассматриваемого типа.