Exact computation of the number of accepting paths of an NTM

Abstract

We look at the problem of counting the exact number of accepting computation paths of a given nondeterministic Turing machine (NTM). We give a deterministic algorithm that runs in time $\widetilde{O}(\sqrt{S})$, where $S$ is the size (number of vertices) of the configuration graph of the NTM, and prove its correctness. Our result implies a deterministic simulation of probabilistic time classes like $\mathsf{PP}$, $\mathsf{BPP}$, and $\mathsf{BQP}$ in the same running time. This is an improvement over the currently best known simulatio by van Melkebeek and Santhanam [SIAM J. Comput., 35(1), 2006], which uses time $\widetilde{O}(S^{1 - \delta})$. It also implies a faster deterministic simulation of the complexity classes $\mathsf{\oplus P}$ and $\mathsf{Mod_k P}$.

Publication
Proceedings of the 4th International Conference on Algorithms and Discrete Applied Mathematics - CALDAM 2018, Guwahati, India
Date