О сложности проверки существования доступа в RelBAC-политиках

В работе исследуется сложность решения следующей задачи. Дана система, разграничение доступа в которой основано на RelBAC-модели, введенной в статьях В. А. Васенина с соавторами, и пара (субъект, объект). Требуется определить, существуют ли условия, при которых субъект может получить заданный доступ к объекту. Мы показываем, что в общем случае эта задача NP-полна. Если же максимальная длина путей ограничена константой, то задача становится полиномиальной.