Access Restriction

Author Grove, Adam J. ♦ Halpern, Joseph Y. ♦ Koller, Daphne
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Asymptotic Conditional Probability ♦ First-order Sentence ♦ Ibm Almaden Research Center ♦ Reasonable Notion ♦ Nontrivial Interval ♦ Liogon Ki Lio69 ♦ Non-unary Predicate Symbol ♦ Liogon Ki ♦ 0-1 Law
Abstract Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences ϕ and θ, we consider the structures with domain {1,..., N} that satisfy θ, and compute the fraction of them in which ϕ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon’kiĭ [Lio69], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon’kiĭ also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study