Kalyanasundaram, Subrahmanyam and Regan, Kenneth W
(2018)
Exact Computation of the Number of Accepting Paths of an NTM.
Springer, pp. 105117.
ISBN 9783319741802
Full text not available from this repository.
(
Request a copy)
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 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.
[error in script]
Actions (login required)

View Item 