A First-Order Isomorphism Theorem

DOI10.1137/S0097539794270236zbMath0874.68124OpenAlexW2043438634MaRDI QIDQ4337654

José L. Balcázar, Neil Immerman, Eric W. Allender

Publication date: 26 May 1997

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

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

zbMATH Keywords

reductioncomplexity classesdescriptive complexityfirst-order projection

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

The isomorphism conjecture for constant depth reductions ⋮ Indistinguishability and First-Order Logic ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Investigations Concerning the Structure of Complete Sets ⋮ A constant-space sequential model of computation for first-order logic ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem

This page was built for publication: A First-Order Isomorphism Theorem