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. Most of these computational problems turn out to be between co-NP and Sigma^p_2.