ON THE COMPUTATIONAL-COMPLEXITY OF SOME CLASSICAL EQUIVALENCE-RELATIONS ON BOOLEAN FUNCTIONS

Authors
BORCHERT B RANJAN D STEPHAN F
Citation
B. Borchert et al., ON THE COMPUTATIONAL-COMPLEXITY OF SOME CLASSICAL EQUIVALENCE-RELATIONS ON BOOLEAN FUNCTIONS, theory of computing systems, 31(6), 1998, pp. 679-693
Citations number
20
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
theory of computing systems → ACNP
Volume
31
Issue
6
Year of publication
1998
Pages
679 - 693
Database
ISI
SICI code
Abstract
The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions , one of them is the Boolean isomorphism relation. Most of these compu tational problems turn out to be between co-NP and Sigma(2)(P).