A First-Order Isomorphism Theorem

DOI10.1137/S0097539794270236MaRDI QIDQ4337654zbMATH OpenOpenAlexFDO

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

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

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)

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

Cited in

(12)

• scientific article; zbMATH DE number 3989686 (Why is no real title available?)
• 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
• Universal first-order logic is superfluous for NL, P, NP and coNP
• Strong Reductions and Isomorphism of Complete Sets
• scientific article; zbMATH DE number 2081095 (Why is no real title available?)
• A comic page for the first isomorphism theorem
• Investigations concerning the structure of complete sets
• Towards stronger depth lower bounds
• The isomorphism conjecture for constant depth reductions

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)