Nonconvergence, undecidability, and intractability in asymptotic problems

DOI10.1016/0168-0072(87)90017-0zbMath0632.03037MaRDI QIDQ1095135

Kevin J. Compton, Saharon Shelah, C. Ward Henson

Publication date: 1987

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2027.42/26912

zbMATH Keywords

permutations; binary functions; binary relations; unary functions; asymptotic probabilities; effective content of asymptotic combinatorics; first-order asymptotic problem; monadic second-order properties

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

05A99: Enumerative combinatorics

Related Items

Counting finite models, Probabilities in first—order logic of a unary function and a binary relation, Zero-one laws with variable probability, On the two kinds of probability in algebra, Finite-model theory -- A personal perspective, A uniform method for proving lower bounds on the computational complexity of logical theories, First order properties of random posets, Metafinite model theory, Zero-one law and definability of linear order, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform method for proving lower bounds on the computational complexity of logical theories
• On random models of finite power and monadic logic
• The computational complexity of logical theories
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Probabilities of First-Order Sentences about Unary Functions
• TWO THEOREMS IN GRAPH THEORY
• An Algorithm for a Minimum Cover of a Graph
• Complexity of the first-order theory of almost all finite structures
• An undecidable problem in finite combinatorics
• A zero-one law for logic with a fixed-point operator
• Application of a Tauberian theorem to finite model theory
• Almost sure theories
• Probabilities on finite models
• Ordered Cycle Lengths in a Random Permutation
• Enumeration of Linear Graphs for Mappings of Finite Sets
• Impossibility of an algorithm for the decision problem in finite classes
• The Expected Number of Components Under a Random Mapping Function