Abstract

Is P≠NP? Is the Riemann hypothesis true? Are there infinitely many twin primes? These conjectures haven’t been proven or disproven, but we have quite a bit of “evidence” for them in the form of proven related sentences.

For example, there exist many decision problems known to be in P, and many that known to be NP-complete, along with schemes for reducing problems to other problems within those clusters. But no single link, in 50 years, has yet been discovered from NP-complete to P. [1] As another example, Zhang [2] showed that for any n, we can find a larger prime such that it’s at most 7·10^7 away from the next prime.

This is the problem of logical uncertainty: to which degree should we believe in these logical sentences? How should we update our beliefs based on the related evidence? One might turn to probability theory for answers. However, the veracity of the sentences is implied by things we assume (the ZF/C axioms), rather than any data we need to observe. Probability theory thus dictates we should assign them probability 1 if they are true, and 0 if they are false, which is clearly impossible to do in general for an algorithm that runs in a finite amount of time.

In this session we will learn about the problem of logical uncertainty, what should a solution to it look like, and how some naive approaches to it fall short [3]. Then, we will examine the “Logical Induction” algorithm [4], which satisfies many desirable properties including being computable, but unfortunately only does so asymptotically and it is not usable in practice. We will conclude with a recap and an outline of a few extra open problems.

[1] Aaronson, S. “The Scientific Case for P≠NP”. https://www.scottaaronson.com/blog/?p=1720 [2] Zhang, Yitang. “Bounded gaps between primes.” Annals of Mathematics 179.3 (2014): 1121-1174. [3] Demski, A. “All Mathematicians are Trollable: Divergence of Naturalistic Logical Updates” https://agentfoundations.org/item?id=815 [4] Demski, A. and Eisenstat, S. “An Untrollable Mathematician”. https://agentfoundations.org/item?id=1750 [5] Garrabrant, Scott, et al. “Logical induction.” https://arxiv.org/abs/1609.03543 (2016)