Presentation	1995/9/22 Complexity Classes Characterizeed by many Computation Paths Ryuhei Uehara,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Counting classes consist of languages defined in terms of the number of accepting (or rejecting) computations of nondeterministic polynomial-time Turing machines. We introduce new counting classes, ManyRP(γ) and ManyBPP(γ), which have γ^P incorrect paths with 1<γ<2, where p is the length of a computation. Here, ManyRP(γ) (or ManyBPP(γ)) corresponds to the class which has more accepting paths than RP (or BPP, respectively.) We define the class exitδ-ManyBPP(γ), which is extended by using a semi-random source, and show that the existence of γ such that exitδ-ManyBPP(γ) = exitδ-BPP implies NP = PSPACE. The result can be seen as an evidence of one of the following inclusions is proper: ManyBPP(γ) ⊆ ManyBPP(γ')⊆ BPP.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	counting classes / probabilistic Turing machines / semi-random sources
Paper #	COMP95-42
Date of Issue

Conference Information
Committee	COMP
Conference Date	1995/9/22(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Complexity Classes Characterizeed by many Computation Paths
Sub Title (in English)
Keyword(1)	counting classes
Keyword(2)	probabilistic Turing machines
Keyword(3)	semi-random sources
1st Author's Name	Ryuhei Uehara
1st Author's Affiliation	Center for Information Science,Tokyo Woman's Christian University()
Date	1995/9/22
Paper #	COMP95-42
Volume (vol)	vol.95
Number (no)	259
Page	pp.pp.-
#Pages	7
Date of Issue