The determination of the computational complexity of multi-agent pathfinding on directed graphs (diMAPF) has been an open research problem for many years. While diMAPF has been shown to be polynomial for some special cases, only recently, it has been established that the problem is NP-hard in general. Further, it has been proved that diMAPF will be in NP if the short solution hypothesis for strongly connected directed graphs is correct. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.

翻译：多年来,确定定向图形多试剂路由的计算复杂性一直是一个公开的研究问题。虽然事实证明对一些特殊案例来说,DIMAPF是多元性的,但直到最近才证实,问题一般是NP硬的。此外,事实证明,如果连接强烈的定向图形的短期解决方案假设正确无误,DIMAPF就会在NP。在本文中,可以证明这一假设是真实的,即使允许同步旋转。