Equivalence Relations, Invariants, and Normal Forms

DOI10.1137/0213042zbMATH Open0545.68035OpenAlexW1997198079MaRDI QIDQ3334985FDOQ3334985

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

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

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)

Cited In (13)

• On polynomial time computation over unordered structures
• Fields of algebraic numbers computable in polynomial time. II
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• The Shrinking Property for NP and coNP
• Complexity classes of equivalence problems revisited
• Form invariance of schema and exact schema theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On complete problems, relativizations and logics for complexity classes
• Relativization of Gurevich’s Conjectures
• Invariance of tautological equations. I: Conjectures and applications
• 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)