Invariant definability and P/poly

DOI10.1007/10703163_10MaRDI QIDQ4263795zbMATH OpenFDO

Authors Johann A. Makowsky

Publication date 25 April 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10703163_10

zbMATH Keywords

complexity classesfinite structuresinvariant definability

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Invariant definability. (Extended abstract)
• Expressibility and Nonuniform Complexity Classes
• On uniformity within \(NC^ 1\)
• scientific article; zbMATH DE number 3885886
• Definability by constant-depth polynomial-size circuits

Cited in

(11)

• Definable invariants of bilinear mappings
• Definability and invariance
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• scientific article; zbMATH DE number 3885886 (Why is no real title available?)
• Fixed-Point Definability and Polynomial Time
• Invariant definability. (Extended abstract)
• scientific article; zbMATH DE number 1936755 (Why is no real title available?)
• Effective definability of Kolchin polynomials
• A characterization of the language invariant families satisfying spectrum exchangeability in polyadic inductive logic
• Generalized implicit definitions on finite structures
• My writing

This page was built for publication: Invariant definability and P/poly

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