The computational complexity of asymptotic problems. I: Partial orders

DOI10.1016/0890-5401(88)90032-6zbMath0665.03028OpenAlexW2036751590MaRDI QIDQ1115860

Kevin J. Compton

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(88)90032-6

zbMATH Keywords

first-order logicpartial ordersPSPACE-completeasymptotic probability0-1 lawsEXPTIME-completeinductive fixed-point logic

Mathematics Subject Classification ID

Partial orders, general (06A06) Probability and inductive logic (03B48) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Partial order complementation graphs, A counterexample in the theory of random orders, Strong 0-1 laws in finite model theory, Random orders of dimension 2, Infinitary logics and 0-1 laws, Limit laws and automorphism groups of random nonrigid structures, A Limit Law of Almost l-partite Graphs, Simple structures axiomatized by almost sure theories, Generic theories as a method for approximating elementary theories

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random orders
• On random models of finite power and monadic logic
• Counting unlabeled structures
• Elementary induction on abstract structures
• The polynomial-time hierarchy
• The number of finite relational structures
• Model theory
• Concerning measures in first order calculi
• Complexity of the first-order theory of almost all finite structures
• A zero-one law for logic with a fixed-point operator
• Relational queries computable in polynomial time
• Almost sure theories
• Alternation
• Asymptotic Enumeration of Partial Orders on a Finite Set
• On nonmonotone inductive definability
• Probabilities on finite models