The computational complexity of asymptotic problems. I: Partial orders

DOI10.1016/0890-5401(88)90032-6MaRDI QIDQ1115860zbMATH OpenOpenAlexFDO

Authors 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

partial ordersfirst-order logicPSPACE-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)

Recommendations

• Nonconvergence, undecidability, and intractability in asymptotic problems
• scientific article; zbMATH DE number 3984616
• Infinitary queries and their asymptotic probabilities. II. Properties definable in least fixed point logic
• Asymptotic conditional probabilities: The non-unary case
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties

Cites work

• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3343737 (Why is no real title available?)
• scientific article; zbMATH DE number 3363533 (Why is no real title available?)
• A zero-one law for logic with a fixed-point operator
• Almost sure theories
• Alternation
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Complexity of the first-order theory of almost all finite structures
• Concerning measures in first order calculi
• Counting unlabeled structures
• Elementary induction on abstract structures
• Model theory
• On nonmonotone inductive definability
• On random models of finite power and monadic logic
• Probabilities on finite models
• Random orders
• Relational queries computable in polynomial time
• The number of finite relational structures
• The polynomial-time hierarchy

Cited in

(16)

• Simple structures axiomatized by almost sure theories
• Limit laws and automorphism groups of random nonrigid structures
• Infinitary logics and 0-1 laws
• A counterexample in the theory of random orders
• Random orders of dimension 2
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Generic theories as a method for approximating elementary theories
• scientific article; zbMATH DE number 176205 (Why is no real title available?)
• Nonconvergence, undecidability, and intractability in asymptotic problems
• Strong 0-1 laws in finite model theory
• scientific article; zbMATH DE number 3855058 (Why is no real title available?)
• Partial order complementation graphs
• Complexity of the first-order theory of almost all finite structures
• scientific article; zbMATH DE number 3984616 (Why is no real title available?)
• On asymptotic probabilities in logics that capture \(\mathrm{DSPACE}(\log n)\) in presence of ordering
• A limit law of almost \(l\)-partite graphs

This page was built for publication: The computational complexity of asymptotic problems. I: Partial orders

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