The power of counting
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 0 references indexed in Scilit: