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

learning theorycomplexity theoryinteractive proofsboolean isomorphism problems

Mathematics Subject Classification ID

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

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)

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

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)