All reports by Author Desh Ranjan:

__
TR96-033
| 6th March 1996
__

Bernd Borchert, Desh Ranjan, Frank Stephan#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

Bernd Borchert, Desh Ranjan, Frank Stephan

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.