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

0-1 lawsasymptotic probabilityEXPTIME-completefirst-order logicinductive fixed-point logicpartial ordersPSPACE-complete

Mathematics Subject Classification ID

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

Review text

The class of partial orders is shown to have 0-1 laws for first-order logic and for inductive fixed-point logic, a logic which properly contains first-order logic. This means that for every sentence in one of these logics the proportion of labeled (or unlabeled) partial orders of size n satisfying the sentence has a limit of either 0 or 1 as n goes to \(\infty\). This limit, called the asymptotic probability of the sentence, is the same for labeled and unlabeled structures. The computational complexity of the set of sentences with asymptotic probability 1 is determined. For first-order logic, it is PSPACE-complete. For inductive fixed-point logic, it is EXPTIME-complete.

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

• 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
• 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?)
• 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)

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

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)