The Formula Isomorphism Problem

DOI10.1137/S0097539798343647zbMath0970.68068OpenAlexW2093712769MaRDI QIDQ4507381

Thomas Thierauf, Manindra Agrawal

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539798343647

zbMATH Keywords

learning theoryinteractive proofscomplexity theoryboolean isomorphism problems

Mathematics Subject Classification ID

Related Items (12)

Some results of Maria Serna on strategic games: complexity of equilibria and models ⋮ Isomorphism testing of read-once functions and polynomials ⋮ Efficient computation of approximate isomorphisms between Boolean functions ⋮ The complexity of game isomorphism ⋮ Isomorphism testing of Boolean functions computable by constant-depth circuits ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Isomorphic implication ⋮ Complexity classes of equivalence problems revisited ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups ⋮ On the isomorphism problem for decision trees and decision lists

This page was built for publication: The Formula Isomorphism Problem