Title :
The power of counting
Author_Institution :
EWH Koblenz Inf., West Germany
Abstract :
An overview of applications and variations of counting in structural complexity theory is provided. It is argued that the capacity for exact counting is closely related with the capacity for nondeterministic complementation. Relations between counting classes and classes requiring uniqueness, such as UP, are discussed, as well as approximate counting and relativized results
Keywords :
computational complexity; UP; nondeterministic complementation; power of counting; structural complexity theory; Basis algorithms; Complexity theory; Noise measurement; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5257
