On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions
Bernd BorchertDesh RanjanFrank StephanPublished in: Electron. Colloquium Comput. Complex. (1996)
Keyphrases
- boolean functions
- equivalence relation
- computational complexity
- rough set theory
- uniform distribution
- rough sets
- numerical data
- np complete
- granular computing
- membership queries
- special case
- functional properties
- rough set approximations
- concept lattice
- dnf formulae
- decision problems
- np hard
- multi valued
- binary relations
- approximation algorithms
- databases
- random graphs