On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions | Zendy

Bernd Borchert | Zendy; Desh Ranjan | Zendy; Frank Stephan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Bernd Borchert,

Desh Ranjan,

Frank Stephan

Publication year - 1998

Publication title -

theory of computing systems

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.479

H-Index - 44

eISSN - 1433-0490

pISSN - 1432-4350

DOI - 10.1007/s002240000109

Subject(s) - equivalence (formal languages) , equivalence relation , boolean function , computational complexity theory , mathematics , boolean expression , isomorphism (crystallography) , product term , boolean circuit , maximum satisfiability problem , discrete mathematics , boolean network , parity function , circuit complexity , two element boolean algebra , algebra over a field , algorithm , pure mathematics , chemistry , electrical engineering , crystal structure , electronic circuit , filtered algebra , crystallography , engineering

. 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 computational problems turn out to be between co-NP and6 , 2 .

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research