Equivalence Relations, Invariants, and Normal Forms

DOI10.1137/0213042MaRDI QIDQ3334985zbMATH OpenOpenAlexFDO

Authors Andreas Blass, Yuri Gurevich

Publication date 1984

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

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

zbMATH Keywords

certificateequivalence relationfirst member probleminvariant problemnormal form problemNP setNP-completeoraclepolynomial timerecognition problemTuring reducibility

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity classes of equivalence problems revisited
• scientific article; zbMATH DE number 3868613
• Rational equivalence relations
• scientific article; zbMATH DE number 3982545
• The complexity of equivalence problems for commutative grammars

Cited in

(15)

• Searching for applicable versions of computable structures
• Fields of algebraic numbers computable in polynomial time. II
• Invariance of tautological equations. I: Conjectures and applications
• Minimum circuit size, graph isomorphism, and related problems
• scientific article; zbMATH DE number 3868613 (Why is no real title available?)
• The Shrinking Property for NP and coNP
• On complete problems, relativizations and logics for complexity classes
• scientific article; zbMATH DE number 5522291 (Why is no real title available?)
• scientific article; zbMATH DE number 5530165 (Why is no real title available?)
• On polynomial time computation over unordered structures
• Relativization of Gurevich’s Conjectures
• scientific article; zbMATH DE number 4197420 (Why is no real title available?)
• Normal forms under Simon's congruence
• Complexity classes of equivalence problems revisited
• Form invariance of schema and exact schema theorem

This page was built for publication: Equivalence Relations, Invariants, and Normal Forms

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