Deciding Polynomial Termination Complexity for VASS Programs

Michal Ajdarów, Antonín Kučera

We show that for every fixed $k\ge 3$, the problem whether the termination/counter complexity of a given demonic VASS is $\mathcal{O}(n^k)$, $\Omega (n^k)$, and $\Theta (n^k)$ is coNP-com…