Nonconvergence, undecidability, and intractability in asymptotic problems

DOI10.1016/0168-0072(87)90017-0zbMath0632.03037OpenAlexW2061456270MaRDI 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

permutationsbinary functionsbinary relationsunary functionsasymptotic probabilitieseffective content of asymptotic combinatoricsfirst-order asymptotic problemmonadic second-order properties

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Complexity of computation (including implicit computational complexity) (03D15) Enumerative combinatorics (05A99)

Related Items

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

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