A First-Order Isomorphism Theorem

DOI10.1137/S0097539794270236zbMATH Open0874.68124OpenAlexW2043438634MaRDI QIDQ4337654FDOQ4337654

José L. Balcázar, Neil Immerman, Eric 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

Recommendations

• scientific article; zbMATH DE number 512825
• scientific article; zbMATH DE number 2081095
• A theorem on the isomorphism property
• scientific article; zbMATH DE number 3989686
• scientific article; zbMATH DE number 3399435
• The first isomorphism theorem and other properties of rings
• A monotone isomorphism theorem
• A characterization of an isomorphism
• An isomorphism theorem for anti-ordered sets
• scientific article; zbMATH DE number 3920758

zbMATH Keywords

complexity classesreductiondescriptive complexityfirst-order projection

Mathematics Subject Classification ID

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

Cited In (10)

• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• The complexity of satisfiability problems: Refining Schaefer's theorem
• A constant-space sequential model of computation for first-order logic
• Indistinguishability and First-Order Logic
• Strong Reductions and Isomorphism of Complete Sets
• Title not available (Why is that?)
• A comic page for the first isomorphism theorem
• The isomorphism conjecture for constant depth reductions
• Investigations Concerning the Structure of Complete Sets
• Title not available (Why is that?)

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

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