Exact Computation of the Number of Accepting Paths of an NTM

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 O˜(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 PP, BPP, and BQP in the same running time. This is an improvement over the currently best known simulation by van Melkebeek and Santhanam [SIAM J. Comput., 35(1), 2006], which uses time O˜(S1−δ). It also implies a faster deterministic simulation of the complexity classes ⊕P and ModkP