Complexity of the first-order theory of almost all finite structures

DOI10.1016/S0019-9958(83)80043-6MaRDI QIDQ3329449zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Etienne Grandjean

Publication date 1983

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(83)80043-6

zbMATH Keywords

first-order sentencePSPACE-completerelational typetheory of almost all directed graphstrue almost everywhereTuring machinezero-one law for graphs

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the Complexity of the First-order Random Theory
• The computational complexity of asymptotic problems. I: Partial orders
• How complex are random graphs in first order logic?
• scientific article; zbMATH DE number 3984616
• An undecidable problem in finite combinatorics

Cited in

(23)

• Nonconvergence, undecidability, and intractability in asymptotic problems
• A logical approach to asymptotic combinatorics I. First order properties
• The computational complexity of asymptotic problems. I: Partial orders
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Distanced graphs
• Infinitary logics and 0-1 laws
• A probabilistic view of Datalog parallelization
• The ^2 fragment of the first-order theory of atomic set constraints is _1⁰-hard
• The Andrews-Curtis conjecture, term rewriting and first-order proofs
• The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
• The complexity of definability by open first-order formulas
• Probabilities of Sentences about Very Sparse Random Graphs
• First-Order Queries on Finite Structures Over the Reals
• scientific article; zbMATH DE number 1907992 (Why is no real title available?)
• Fifty years of the spectrum problem: survey and new results
• The Exact Complexity of the First-Order Logic Definability Problem
• An Asymptotic Analysis of Probabilistic Logic Programming, with Implications for Expressing Projective Families of Distributions
• On the expressive power of counting
• Hard problems on random graphs
• Asymptotic truth-value laws in many-valued logics
• Finite-model theory -- A personal perspective
• A uniform method for proving lower bounds on the computational complexity of logical theories
• 0-1 laws and decision problems for fragments of second-order logic

This page was built for publication: Complexity of the first-order theory of almost all finite structures

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