Title :
A survey on counting classes
Author :
Gundermannn, Thomas ; Nasser, Nasser Ali ; Wechsung, Gerd
Abstract :
Consideration is given to polynomial-time machines. Among these classes are EP and PP. The authors prove PEP[log] 25 PP, investigate the Boolean closure BC(EP) of EP, and give a relativization principle which allows them to completely separate BC(EP) in a suitable relativized world and to give simple proofs for known relativization results. Further results concerning the relationships of such classes in unrelativized and relativized worlds are given
Keywords :
Boolean algebra; computational complexity; Boolean closure; EP; PP; counting classes; polynomial-time machines; relativization principle; Character generation; Clocks; Equations; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113963
