Equivalence Relations, Invariants, and Normal Forms

DOI10.1137/0213042zbMath0545.68035OpenAlexW1997198079MaRDI QIDQ3334985

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 problempolynomial timeTuring reducibilityoraclecertificateequivalence relationinvariant 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)

Related Items (8)

Relativization of Gurevich’s Conjectures ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Fields of algebraic numbers computable in polynomial time. II ⋮ The Shrinking Property for NP and coNP ⋮ On Complete Problems, Relativizations and Logics for Complexity Classes ⋮ Complexity classes of equivalence problems revisited ⋮ Searching for applicable versions of computable structures ⋮ On polynomial time computation over unordered structures

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