Exact computation of the number of accepting paths of an NTM

Subrahmanyam Kalyanasundaram; Kenneth W. Regan

doi:10.1007/978-3-319-74180-2_9

Exact computation of the number of accepting paths of an NTM

Subrahmanyam Kalyanasundaram
, Kenneth W. Regan

Department of Computer Science and Engineering

Indian Institute of Technology Hyderabad

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 (Formula presented), 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 (Formula presented). It also implies a faster deterministic simulation of the complexity classes (Formula presented) and (Formula presented).

Original language	English
Title of host publication	Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings
Editors	B.S. Panda, Partha P. Goswami
Publisher	Springer Verlag
Pages	105-117
Number of pages	13
ISBN (Print)	9783319741796
DOIs	https://doi.org/10.1007/978-3-319-74180-2_9
State	Published - 2018
Event	4th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2018 - Guwahati, India Duration: Feb 15 2018 → Feb 17 2018

Publication series

Name	Communications in Computer and Information Science
Volume	10743 LNCS
ISSN (Print)	1865-0929

Conference

Conference	4th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2018
Country/Territory	India
City	Guwahati
Period	02/15/18 → 02/17/18

Access to Document

10.1007/978-3-319-74180-2_9

Cite this

Kalyanasundaram, S., & Regan, K. W. (2018). Exact computation of the number of accepting paths of an NTM. In B. S. Panda, & P. P. Goswami (Eds.), Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings (pp. 105-117). (Communications in Computer and Information Science; Vol. 10743 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-74180-2_9

@inproceedings{5186401798974b9eb93924b128476ea7,

title = "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 (Formula presented), 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 (Formula presented). It also implies a faster deterministic simulation of the complexity classes (Formula presented) and (Formula presented).",

author = "Subrahmanyam Kalyanasundaram and Regan, \{Kenneth W.\}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.; 4th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2018 ; Conference date: 15-02-2018 Through 17-02-2018",

year = "2018",

doi = "10.1007/978-3-319-74180-2\_9",

language = "English",

isbn = "9783319741796",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "105--117",

editor = "B.S. Panda and Goswami, \{Partha P.\}",

booktitle = "Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings",

address = "Germany",

}

Kalyanasundaram, S & Regan, KW 2018, Exact computation of the number of accepting paths of an NTM. in BS Panda & PP Goswami (eds), Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings. Communications in Computer and Information Science, vol. 10743 LNCS, Springer Verlag, pp. 105-117, 4th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2018, Guwahati, India, 02/15/18. https://doi.org/10.1007/978-3-319-74180-2_9

Exact computation of the number of accepting paths of an NTM. / Kalyanasundaram, Subrahmanyam; Regan, Kenneth W.
Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings. ed. / B.S. Panda; Partha P. Goswami. Springer Verlag, 2018. p. 105-117 (Communications in Computer and Information Science; Vol. 10743 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Exact computation of the number of accepting paths of an NTM

AU - Kalyanasundaram, Subrahmanyam

AU - Regan, Kenneth W.

N1 - Publisher Copyright: © Springer International Publishing AG 2018.

PY - 2018

Y1 - 2018

N2 - 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 (Formula presented), 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 (Formula presented). It also implies a faster deterministic simulation of the complexity classes (Formula presented) and (Formula presented).

AB - 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 (Formula presented), 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 (Formula presented). It also implies a faster deterministic simulation of the complexity classes (Formula presented) and (Formula presented).

UR - https://www.scopus.com/pages/publications/85042092619

U2 - 10.1007/978-3-319-74180-2_9

DO - 10.1007/978-3-319-74180-2_9

M3 - Conference contribution

AN - SCOPUS:85042092619

SN - 9783319741796

T3 - Communications in Computer and Information Science

SP - 105

EP - 117

BT - Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings

A2 - Panda, B.S.

A2 - Goswami, Partha P.

PB - Springer Verlag

T2 - 4th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2018

Y2 - 15 February 2018 through 17 February 2018

ER -

Exact computation of the number of accepting paths of an NTM

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this