The Formula Isomorphism Problem

DOI10.1137/S0097539798343647MaRDI QIDQ4507381zbMATH OpenOpenAlexFDO

Authors Manindra Agrawal, Thomas Thierauf

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

boolean isomorphism problemscomplexity theoryinteractive proofslearning theory

Mathematics Subject Classification ID

Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32)

Recommendations

• AN ISOMORPHISM PROBLEM
• scientific article; zbMATH DE number 4154700
• The isometric equivalence problem
• The Word Problem Versus the Isomorphism Problem
• scientific article; zbMATH DE number 3952822
• scientific article; zbMATH DE number 549861
• Quadratic forms and the graph isomorphism problem
• scientific article; zbMATH DE number 7147443
• The equivalence problem
• scientific article; zbMATH DE number 1302479

Cited in

(16)

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

This page was built for publication: The Formula Isomorphism Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507381)