Exact Computation of the Number of Accepting Paths of an NTM

Kalyanasundaram, Subrahmanyam and Regan, Kenneth W (2018) Exact Computation of the Number of Accepting Paths of an NTM. Springer, pp. 105-117. 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]

IITH Creators:	IITH Creators ORCiD Kalyanasundaram, Subrahmanyam UNSPECIFIED
Item Type:	Book
Subjects:	Computer science
Divisions:	Department of Computer Science & Engineering
Depositing User:	Team Library
Date Deposited:	13 Feb 2018 04:17
Last Modified:	13 Feb 2018 04:17
URI:	http://raiithold.iith.ac.in/id/eprint/3775
Publisher URL:	http://doi.org/10.1007/978-3-319-74180-2_9
Related URLs:	Google Scholar

Actions (login required)

View Item

Statistics for this ePrint Item