Complexity Theory

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 $\widetilde{O}(\sqrt{S})$, where $S$ is the size (number of …