О сложности решения уравнений над графами

Аннотация

В данной работе исследуется проблема определения совместности систем уравнений без констант над
произвольным фиксированным конечным графом.
При этом граф фиксирован, а входом является произвольная система уравнений в языке графов без констант.
Дается критерий NP-полноты и полиномиальной разрешимости
этой проблемы. Также доказывается ее генерическая разрешимость за полиномиальное время.