On the computational complexity of some classical equivalence relations on boolean functions

DOI10.1007/s002240000109zbMath0916.68059OpenAlexW1997240046MaRDI QIDQ1272598

K. Appert

Publication date: 3 January 1999

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://publikationen.bibliothek.kit.edu/78097/2796

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Some results of Maria Serna on strategic games: complexity of equilibria and models ⋮ Isomorphism testing of read-once functions and polynomials ⋮ The complexity of game isomorphism ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ Isomorphic implication ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ The minimum equivalent DNF problem and shortest implicants

This page was built for publication: On the computational complexity of some classical equivalence relations on boolean functions