The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in $NP \cap coNP$ but not known to be in $P$. The currently best algorithms have runtime $2^{\Theta(n)}$ where $n$ is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime $2^{O(\sqrt{n}\log n)}$. We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.
翻译：ARRIVAL的问题是根据简单的(确定性)假随机行走来决定沿着方向图边缘行驶的火车的命运。 问题在于$NP = cap coNP$, 但不是已知的$P$。 目前最好的算法运行时间为 2 ⁇ Theta (n) $, 其中美元是顶点数。 这不比仅仅进行假随机行走要好得多。 我们开发了运行时间为 2 ⁇ O (\\ qrt{n ⁇ log n) 的次特效算法。 如果图表几乎是周期性的, 我们也给出了多数值算法。 这两个结果都来自解决ARRIVAL 案例的新的通用方法 。
相关内容
微信扫码咨询专知VIP会员