Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-033 | 6th March 1996 00:00

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

RSS-Feed




TR96-033
Authors: Bernd Borchert, Desh Ranjan, Frank Stephan
Publication: 17th May 1996 18:09
Downloads: 896
Keywords: 


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.



ISSN 1433-8092 | Imprint