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

NP-completerecognition problemcertificateequivalence relationpolynomial timeoracleTuring reducibilityinvariant problemfirst member problemnormal form problemNP set

Mathematics Subject Classification ID

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

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

(14)

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

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)